Сортировка списка целых чисел в список списков по суммам цифр

Я пытаюсь написать функцию Python для сортировки списка чисел в список списков чисел, где каждый подсписок содержит только числа, которые имеют сумму цифр индекса подсписка в большем списке.

Так, например, для всех чисел от 1 до 25 должен получиться список таких списков:

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

У меня пока есть следующий код:

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

Очевидно, что это неэффективно, потому что приходится перебирать весь список целых чисел снова и снова для каждой суммы цифр от 0 до максимальной суммы цифр.

Кроме того, изначально предполагается, что максимальная сумма цифр в 9 раз превышает длину максимального целого числа. Чтобы было ясно, я хочу всегда иметь подсписок для возможной нулевой суммы цифр, чтобы я мог ссылаться на подсписок определенной суммы цифр по индексу списка списков.

Я хочу, чтобы функция перебирала каждое целое число в списке ровно один раз и добавляла его в правильный подсписок.

Буду признателен за любую помощь или информацию по этому поводу.


python list number-theory
person L85376    schedule 01.11.2016    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Следующий цикл выполняется ровно один раз для данных и возвращает словарь, ключи которого являются суммами, а значения — элементами, соответствующими этой сумме:

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]}

Вы можете отсортировать значения словаря на основе сумм, чтобы получить список, но я думаю, что сохранение ваших данных в виде словаря может послужить вам лучше.

person Moses Koledoye    schedule 01.11.2016
comment
Это хорошо, если по какой-то причине вывод не обязательно должен быть списком. Эффективно выполняет то же самое, не имея кучу пустых списков. - person beeftendon; 02.11.2016

arrow_upward
2
arrow_downward

Если вы не возражаете против использования itertools, вот способ, который должен быть более эффективным.

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]]

Как это работает здесь: используйте sorted() для сортировки исходного списка по сумме цифр целых чисел, чтобы вы могли использовать метод groupby() для группировки списка по сумме цифр, а затем прокручивать группы и преобразовывать целые числа в каждой группе в список.

Обновление: чтобы получить список, в котором сумма цифр подсписка равна индексу, вы можете сначала создать словарь:

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]]
person Psidom    schedule 01.11.2016
comment
Это именно то, что ищет спрашивающий? Я не думаю, что это помещает внутренние списки в индекс, равный их сумме цифр. Вместо этого он просто группирует и сортирует их по сумме цифр. - person beeftendon; 02.11.2016

arrow_upward
0
arrow_downward

Если вам нужно решение, которое оставляет пустые списки, а эффективность использования пространства не является вашей главной задачей, я бы использовал список кортежей:

>>> 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]]
>>>

Итак, предположим, что ваши данные гораздо более разрежены:

>>> 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]]
>>>

И вы можете получить доступ к своим данным как таковым:

>>> list_of_lists[17]
[89]
>>> list_of_lists[8]
[]
>>>
person juanpa.arrivillaga    schedule 01.11.2016

arrow_upward
0
arrow_downward

Очень просто:

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)
person Eric    schedule 01.11.2016