Как сравнить все возможности объединения набора списков чисел с запрошенным списком чисел в Python?

Question

У меня есть список списков, в которых есть словари:

[ 
    [{'A': [35, 64, 72]}, {'B': [42, 55, 23]}, {'C': [17, 23, 55]}],
    [{'A': [35, 64, 72]}, {'B': [42, 55, 23]}, {'C': [17, 23, 55]}],
    [{'D': [72]}, {'E': [42]}]
]

И у меня есть другой список, запрошенный список, который выглядит так:

[35, 64, 72, 42, 17, 23, 55]

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

Итак, в этом случае я бы хотел, чтобы результат был

['A', 'C', 'E']

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

Я действительно надеюсь, что объясняю это правильно, и мне очень жаль, если это что-то простой уже спросил. Я ничего не смог найти об этом, но, возможно, я неправильно описываю свою проблему.

Любой был бы очень признателен! Я застрял ..

Answer 1

OP добавил требования в комментариях под этим вопросом. Он достаточно изменен, хотя и связан, поэтому я решил оставить этот ответ на месте (чтобы ответить на вопрос, как показано) и добавить отдельный ответ , относящийся к этому делу.

Проблема разбивается на две части.

1. Перевод ваших входных данных в более удобный формат:

data_in = [ 
    [{'A': [35, 64, 72]}, {'B': [42, 55, 23]}, {'C': [17, 23, 55]}],
    [{'A': [35, 64, 72]}, {'B': [42, 55, 23]}, {'C': [17, 23, 55]}],
    [{'D': [72]}, {'E': [42]}]
]

target_list = [35, 64, 72, 42, 17, 23, 55]

data = {}
for sublist in data_in:
    for dct in sublist:
        data.update({k: set(v) for k, v in dct.items()})

target = set(target_list)
        
print(data)
# {'A': {64, 72, 35}, 'B': {42, 23, 55}, 'C': {17, 55, 23}, 'D': {72}, 'E': {42}}

print(target)
# {64, 35, 72, 42, 17, 55, 23}

Сделав это, решаем интересную задачу. Это можно сделать с помощью рекурсивного подхода:

def find_combos(target, items):
    for i, (k, v) in enumerate(items):
        if not (v - target):
            remaining = target - v
            if remaining:                
                for lst in find_combos(remaining, items[i + 1 :]):
                    yield [k] + lst
            else:
                yield [k]


for combo in find_combos(target, list(data.items())):
    print(combo)

Печать:

['A', 'C', 'E']

Answer 2

После дополнительных разъяснений OP относительно требований:

Однако я заметил, что забыл упомянуть о требовании. Комбинация всегда должна содержать ровно 1 букву каждого из основных списков. Итак, в этом примере должен быть один из A, B, C, другой из A, B, C и один из D, E.

Я решил оставить свой исходный ответ и добавить его рядом с ним для немного другого варианта использования.

Все еще предварительно обрабатывают входные данные, хотя и не так сильно - на этот раз список словарей (снова с наборами в качестве значений словаря):

data_in = [ 
    [{'A': [35, 64, 72]}, {'B': [42, 55, 23]}, {'C': [17, 23, 55]}],
    [{'A': [35, 64, 72]}, {'B': [42, 55, 23]}, {'C': [17, 23, 55]}],
    [{'D': [72]}, {'E': [42]}]
]

target_list = [35, 64, 72, 42, 17, 23, 55]

data = []
for sublist in data_in:
    dct = {}
    for dct_in in sublist:        
        dct.update({k: set(v) for k, v in dct_in.items()})
    data.append(dct)

target = set(target_list)

print(data)
# [{'A': {64, 72, 35}, 'B': {42, 23, 55}, 'C': {17, 55, 23}}, {'A': {64, 72, 35}, 'B': {42, 23, 55}, 'C': {17, 55, 23}}, {'D': {72}, 'E': {42}}]

print(target)    
# {64, 35, 72, 42, 17, 55, 23}

И снова рекурсивное решение, но немного другое, чем before:

def find_combos(target, data):
    for k, v in data[0].items():
        if not (v - target):
            remaining_data = data[1:]
            remaining_target = target - v
            if remaining_data:
                for lst in find_combos(remaining_target, remaining_data):
                    yield [k] + lst
            elif not remaining_target:
                yield [k]

for combo in find_combos(target, data):
    print(combo)

Это дает:

['A', 'C', 'E']
['C', 'A', 'E']

Если вы хотите избежать "дубликатов" (смотрите только на ключи здесь - это зависит от тех же ключей, имеющих одинаковые связанные значения во входных данных), вы можете сделать что-то вроде этого:

combos_dict = {tuple(sorted(combo)): combo
               for combo in find_combos(target, data)}

uniq_combos = list(combos_dict.values())
print(uniq_combos)

, что дает:

[['A', 'C', 'E']]

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

• При предварительной обработке входных данных используйте from collections import Counter и замените set на Counter в двух местах, где он появляется, что даст:

data = [{'A': Counter({35: 1, 64: 1, 72: 1}), 'B': Counter({42: 1, 55: 1, 23: 1}), 'C': Counter({17: 1, 23: 1, 55: 1})}, {'A': Counter({35: 1, 64: 1, 72: 1}), 'B': Counter({42: 1, 55: 1, 23: 1}), 'C': Counter({17: 1, 23: 1, 55: 1})}, {'D': Counter({72: 1}), 'E': Counter({42: 1})}]

target = Counter({35: 1, 64: 1, 72: 1, 42: 1, 17: 1, 23: 1, 55: 1})

• Затем замените

        if not (v - target):

на

        if all(target.get(kk, 0) >= vv for kk, vv in v.items()):

• Наконец, замените

            remaining_target = target - v

на

            remaining_target = target.copy()
            for kk, vv in v.items():
                remaining_target[kk] -= vv
                if remaining_target[kk] == 0:
                    del remaining_target[kk]