Как найти все комбинации пар, в которых ни один из элементов комбинации не имеет общего первого или последнего значения? ⇐ 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_of_connections = 3

# 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:
# check if numbers are the same
if collection[0][0] == collection[1][0] or collection[0][0] == collection[2][0] or collection[1][0] == collection[2][0]:
continue
# check if letters are the same
if collection[0][1] == collection[1][1] or collection[0][1] == collection[2][1] or collection[1][1] == collection[2][1]:
continue
# all clear--add the collection! :)
all_good_combinations.append(collection)

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

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