Все комбинации в списке списка или словаре

Question

Использование Python:

У меня есть словарь, где «ключ» представляет ценность монеты. И «стоимость» представляет номер этой монеты.

Например:

dict =  {2: [0], 1: [0], 0.5: [0], 0.2: [0], 0.1: [0], 0.05: [1], 0.02: [1, 1, 1, 1], 0.01: [1, 1, 1]}

или

dict = {2: [], 1: [], 0.5: [], 0.2: [], 0.1: [], 0.05: [1], 0.02: [1, 1, 1, 1], 0.01: [1, 1, 1]}

или

dict = {2: 0, 1: 0, 0.5: 0, 0.2: 0, 0.1: 0, 0.05: 1, 0.02: 4, 0.01: 3}

(Я не уверен, какой из них лучше использовать - его также можно представить в виде списка из 8 целых чисел, например, [0,0,0,0,0,1,4,3] или списка списки, например [[], [], [], [], [], [1], [1,1,1,1], [1,1,1]])

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

РЕДАКТИРОВАТЬ: я понял, что я хочу сделать со словарями невозможно, так как вы не можете иметь несколько назначений для одного имени ключа: как можно использовать функцию itertools.combination (iterable, r) для возврата списка кортежей?

Answer 1

Я думаю, что самый простой способ решить эту проблему - использовать itertools.combinations.

Чтобы использовать это, вам сначала нужно конвертировать dict монет в list монет:

coins = {2: 0, 1: 0, 0.5: 0, 0.2: 0, 0.1: 0, 0.05: 1, 0.02: 4, 0.01: 3}
# stores a list of all coin values, ie [0.2, 0.2, 1] if one has two 20c and 1 $1
coin_list = []
for value, count in coins.items():
    if count > 0:
        coin_list += [value] * count

Затем можно использовать itertools.combinations, чтобы получить каждую возможную комбинацию для каждого возможного размера комбинации, суммировать ее и сохранить, если на выходе dict.

Поскольку вы хотите хранить каждую возможную комбинацию монет для каждого значения, вы можете превратить каждый элемент в dict в set из collections.Counter. set будет хранить только уникальное количество монет:

import itertools
import collections
output_dict = dict()
for comb_size in range(len(coin_list)):
    # gets every combination of every size from coin_list
    for combination in itertools.combinations(coin_list, comb_size):
        # sums up all coins in combination
        value = sum(combination)
        # get the set of existing coins for value/create if it doesn't exist
        value_set = output_dict.get(value, set())
        # collections.Counter counts up each coin in a combination
        counter = collections.Counter(combination)
        # we need to convert counter to a hashable form to add it to a set()
        value_set.add(tuple(sorted(counter.items())))
        output_dict[value] = value_set

Наконец, поскольку суммирование чисел с плавающей запятой может привести к странным результатам (например, 0.1 + 0.2 = 0.300000001), при печати вы можете округлить значение суммы до ближайшего цента (и использовать модуль pprint, чтобы сделать форматирование лучше):

import pprint
pprint.pprint({round(x, 2): y for x,y in output_dict.items()})

Что вывело бы dict из set для каждой суммы достоинства монеты. Каждый set содержит tuples пар (стоимость монеты, количество монет), то есть для 3 центов можно иметь либо 3 * 1c монеты (((0.01, 3),)), либо 1c + 2c (((0.01, 1), (0.02, 1))):

{0: {()},
 0.01: {((0.01, 1),)},
 0.02: {((0.02, 1),), ((0.01, 2),)},
 0.03: {((0.01, 3),), ((0.01, 1), (0.02, 1))},
 0.04: {((0.02, 2),), ((0.01, 2), (0.02, 1))},
 0.05: {((0.01, 1), (0.02, 2)), ((0.05, 1),), ((0.01, 3), (0.02, 1))},
 0.06: {((0.02, 3),)},
 0.07: {((0.01, 1), (0.02, 3))},
 0.08: {((0.01, 2), (0.02, 3))},
 0.09: {((0.01, 3), (0.02, 3))},
 0.1: {((0.01, 3), (0.02, 1), (0.05, 1)), ((0.01, 2), (0.02, 4))},
 0.11: {((0.01, 3), (0.02, 4))},
 0.12: {((0.01, 3), (0.02, 2), (0.05, 1))},
 0.13: {((0.01, 2), (0.02, 3), (0.05, 1)), ((0.02, 4), (0.05, 1))},
 0.14: {((0.01, 1), (0.02, 4), (0.05, 1)), ((0.01, 3), (0.02, 3), (0.05, 1))},
 0.15: {((0.01, 2), (0.02, 4), (0.05, 1))}}