Liste der Ganzzahlen in die Liste der Listen nach Ziffern summieren

Question

Ich versuche, eine Python-Funktion zu schreiben, um eine Liste von Zahlen in eine Liste von Listen von Nummern zu sortieren, wobei jede Unterliste nur Zahlen enthält, die die Ziffernsumme des Index von haben die Unterliste in der größeren Liste.

So zum Beispiel für alle Zahlen von 1 bis 25, soll es eine Liste von Listen wie folgt ergeben:

[[], [1, 10], [2, 11, 20], [3, 12, 21], [4, 13, 22], [5, 14, 23], [6, 15, 24], [7, 16], [8, 17], [9, 18], [19]] 

Ich habe den folgenden Code so weit:

def digit_sum(integer_data_type): 
    int_string = str(integer_data_type) 
    sum = 0 
    for digits in int_string: 
     sum += int(digits) 
    return sum 


def organize_by_digit_sum(integer_list): 
    integer_list.sort() 
    max_ds = 9*len(str(max(integer_list)))+1 
    list_of_lists = [] 
    current_ds = 0 
    while current_ds <= max_ds: 
      current_list = [] 
      for n in integer_list: 
        if digit_sum(n) == current_ds: 
          current_list.append(n) 
      list_of_lists.append(current_list) 
      current_ds += 1 
    return list_of_lists 

Offensichtlich ist dies ineffizient, weil es die gesamte Integer-Liste für jede Ziffernsumme von 0 bis zur maximalen Ziffernsumme immer wieder durchlaufen muss.

Außerdem nimmt es anfänglich an, dass die maximale Ziffernsumme das 9-fache der Länge der maximalen Ganzzahl ist. Um es klar zu sagen, ich möchte immer eine Unterliste für die mögliche Ziffernsumme von Null haben, so dass ich auf die Unterliste einer bestimmten Ziffernsumme durch den Index der Listenliste verweisen kann.

Ich möchte die Funktion nur jede Integer in der Liste genau einmal durchlaufen und an die richtige Unterliste anhängen.

Ich würde jede Hilfe oder Einsichten dazu schätzen.

Answer 1

Wenn Sie nichts gegen itertools, hier ist ein Weg, der effizienter sein sollte.

from itertools import groupby 
digit_sum = lambda x: sum(int(i) for i in str(x)) 
[list(g) for _, g in groupby(sorted(range(1,26), key = digit_sum), key = digit_sum)] 
            # ^^^^^^^^^^ replace this with your actual data 
# [[1, 10], 
# [2, 11, 20], 
# [3, 12, 21], 
# [4, 13, 22], 
# [5, 14, 23], 
# [6, 15, 24], 
# [7, 16, 25], 
# [8, 17], 
# [9, 18], 
# [19]] 

So wie es hier funktioniert: sorted() benutzen, um Ihre ursprüngliche Liste von der Ziffer Summe der ganzen Zahlen zu sortieren, so dass Sie Ihre Liste durch die Ziffer Summe groupby() Methode zu gruppieren und dann die Schleife durch die Gruppen verwenden können und konvertieren die Ganzzahlen in jeder Gruppe zu einer Liste.

aktualisieren: Liste erhalten, wo die Ziffer Summe der Teilliste auf den Index gleich ist, können Sie zunächst ein Wörterbuch erstellen:

dict_ = dict((k,list(g)) for k, g in groupby(sorted(range(1,26), key = digit_sum), key = digit_sum)) 

dict_ 
# {1: [1, 10], 
# 2: [2, 11, 20], 
# 3: [3, 12, 21], 
# 4: [4, 13, 22], 
# 5: [5, 14, 23], 
# 6: [6, 15, 24], 
# 7: [7, 16, 25], 
# 8: [8, 17], 
# 9: [9, 18], 
# 10: [19]} 

[dict_.get(key, []) for key in range(max(dict_.keys()))] 
# [[], 
# [1, 10], 
# [2, 11, 20], 
# [3, 12, 21], 
# [4, 13, 22], 
# [5, 14, 23], 
# [6, 15, 24], 
# [7, 16, 25], 
# [8, 17], 
# [9, 18]] 

Answer 2

Wenn Sie eine Lösung wollen, die leere Listen verlässt, und Raumeffizienz ist nicht Ihr Hauptanliegen, würde ich eine Liste von Tupeln verwenden:

>>> def digit_sum(digits): 
... total = 0 
... while digits != 0: 
...  total += digits % 10 
...  digits = digits // 10 
... return total 
... 
>>> numbers = list(range(1,26)) 
>>> pairs = sorted((digit_sum(n),n) for n in numbers) 
>>> pairs 
[(1, 1), (1, 10), (2, 2), (2, 11), (2, 20), (3, 3), (3, 12), (3, 21), (4, 4), (4, 13), (4, 22), (5, 5), (5, 14), (5, 23), (6, 6), (6, 15), (6, 24), (7, 7), (7, 16), (7, 25), (8, 8), (8, 17), (9, 9), (9, 18), (10, 19)] 
>>> maximum_sum = pairs[-1][0] 
>>> list_of_lists = [[] for _ in range(maximum_sum+1)] 
>>> for pair in pairs: 
... list_of_lists[pair[0]].append(pair[1]) 
... 
>>> list_of_lists 
[[], [1, 10], [2, 11, 20], [3, 12, 21], [4, 13, 22], [5, 14, 23], [6, 15, 24], [7, 16, 25], [8, 17], [9, 18], [19]] 
>>> 

So nehme Ihre Daten sind viel spärlicher:

>>> numbers = [4,25,47,89] 
>>> pairs = sorted((digit_sum(n),n) for n in numbers) 
>>> pairs 
[(4, 4), (7, 25), (11, 47), (17, 89)] 
>>> maximum_sum = pairs[-1][0] 
>>> list_of_lists = [[] for _ in range(maximum_sum+1)] 
>>> for pair in pairs: 
... list_of_lists[pair[0]].append(pair[1]) 
... 
>>> from pprint import pprint 
>>> pprint(list_of_lists,width=2) 
[[], 
[], 
[], 
[], 
[4], 
[], 
[], 
[25], 
[], 
[], 
[], 
[47], 
[], 
[], 
[], 
[], 
[], 
[89]] 
>>> 

Und Sie können Ihre Daten als solche Zugang:

>>> list_of_lists[17] 
[89] 
>>> list_of_lists[8] 
[] 
>>> 

Answer 3

Die folgenden Schleifen genau einmal auf den Daten und gibt ein Wörterbuch, dessen Schlüssel die Summen und Werte sind die Elemente, die zu dieser Summe entsprechen:

from collections import defaultdict 
from pprint import pprint 

def group_by_sum(lst): 
    d = defaultdict(list) 
    for i in lst: 
     d[sum(int(j) for j in str(i))].append(i) 
    return d 

pprint(group_by_sum(range(1, 25))) 
# {1: [1, 10], 
# 2: [2, 11, 20], 
# 3: [3, 12, 21], 
# 4: [4, 13, 22], 
# 5: [5, 14, 23], 
# 6: [6, 15, 24], 
# 7: [7, 16], 
# 8: [8, 17], 
# 9: [9, 18], 
# 10: [19]} 

Sie können die Wörterbuch-Werte auf der Summe basierten sortieren, eine Liste zu haben, aber ich denke, Ihre Daten als Wörterbuch halten könnten Sie besser dienen.

Answer 4

Sehr einfach:

list_of_lists = [[] for i in range(11)] 

for i in range(25): 
    digit_sum = sum(int(i) for i in str(i)) 
    list_of_lists[digit_sum].append(i) 

print (list_of_lists)