Как найти все комбинации пар, в которых ни один из элементов комбинации не имеет общего первого или последнего значения? ⇐ Python

[Anonymous]

У меня есть список пар цифр и букв, например:

Код: Выделить всё

all_edges_array = [
[1,'a'],[1,'b'],[1,'c'],
[2,'c'],[2,'d'],
[3,'b'],[3,'c']
]

Обратите внимание, что входные пары не являются векторным произведением используемых букв и цифр, например, [2, 'a'] отсутствует.
Я хочу эффективно находить комбинации некоторого количества пар, чтобы внутри группы никакие две пары не использовали одно и то же число или одну и ту же букву.
Для приведенного выше ввода всего должно быть 5 результатов: [([1, 'a'], [2, 'c'], [3, 'b']), ([1, 'a'], [2, 'd'], [3, 'b']), ([1, 'a'], [2, 'd' ], [3, 'c']), ([1, 'b'], [2, 'd'], [3, 'c']), ([1, 'c'], [2, ' d'], [3, 'b'])].
Другие комбинации недопустимы: например, ([1, 'a'], [1, 'b'], [3, 'c']) содержит две пары, использующие один и тот же номер (1) и ([1, 'b'], [2, 'c'], [3, ' b']) содержит две пары, использующие одну и ту же букву (b).
У меня есть код, который перебирает это, используя itertools.combinations и затем фильтруя результат:

Код: Выделить всё

from itertools import combinations

number_letter_dict = {1:['a','b','c'], 2:['c','d'], 3:['b','c']}

# create the edges based on the connections in the number_letter_dict
all_edges_array = []
for key in number_letter_dict.keys():
for item in number_letter_dict[key]:
all_edges_array.append([key, item])

# get the number of connections relative to the number of keys in dict
number_of_connections = len(number_letter_dict.keys())

# Find all 35 combinations
all_combinations_array = list(combinations(all_edges_array, number_of_connections))

# cut down the list of combinations to what I actually need
all_good_combinations = []
for collection in all_combinations_array:
duplicated_item = False
seen_indices = []
for item in collection:
if item[0] in seen_indices:
duplicated_item = True
break
if item[1] in seen_indices:
duplicated_item = True
break
seen_indices.append(item[0])
seen_indices.append(item[1])
# all clear--add the collection! :)
if not duplicated_item:
all_good_combinations.append(collection)

Это работает, но неэффективно — для фактического ввода требуется неприемлемо много времени. Создается гораздо больше комбинаций, чем допустимых, и чем больше ребер и соединений, тем хуже становится.
Как можно улучшить этот алгоритм? Я предполагаю, что это в первую очередь предполагает отказ от создания недопустимых комбинаций, но я не вижу способа добиться этого.
Я нашел предыдущий вопрос и ответ на Python: Как генерировать все комбинации списки кортежей без повторения содержимого кортежа, но это не отвечает на мой вопрос. Ответы там предполагают, что входные данные содержат все возможные пары (а также что количество пар в комбинациях должно быть равно количеству возможностей для более ограниченного элемента пары).
РЕДАКТИРОВАТЬ : Я заменил часть свернутого кода, потому что это вызвало больше путаницы, чем спасло: упс? Кроме того, этот код работает. Если дать ему достаточно времени, он обязательно даст правильный ответ. Тем не менее, тратить пять дней на обработку одного изображения — это, на мой вкус, недостаточно быстро.

Подробнее здесь: https://stackoverflow.com/questions/791 ... combinatio