Поиск циклов между числами в списке наборов ⇐ Python

[Anonymous]

Данный список наборов типа:

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

sets=[{1,2},{2,3},{1,3}]

продукт (1,2,3) будет сгенерирован дважды в itertools.product(*sets), поскольку литералы (1,2,3 ) и (2,3,1), потому что есть цикл. Если цикла нет, то не будет и дублирования, хотя между наборами может быть много общего.
Петля существует, когда вы можете перемещаться от одного числа в наборе к другому числу в наборе. набора, затем на тот же номер в другом наборе и вернитесь к исходному номеру, например. 1>2-->2>3-->3>1-->1, где '-->' указывает перемещение между наборами, а '>' указывает на перемещение внутри набора. Самый маленький цикл будет включать пару чисел, общих для двух наборов, например. a>b-->b>a-->a.
Какой тип графовой структуры я мог бы использовать для представления этого? Я попытался представить каждый набор как узел, а затем указать, какие наборы с какими связаны, но это неправильно, поскольку для [{1,2},{1,3},{1,4}], между всеми множествами есть связь (общая единица), но петли нет. Я также пытался присвоить букву каждому числу в каждом наборе, но это тоже кажется неправильным, поскольку тогда я не знаю, как отличить циклы внутри набора.
Это было вызвано вопросом о создании уникальных продуктов.
Примерные наборы, подобные следующему (который имеет тривиальный цикл 4>17--17>4< /code> и более длинные циклы, например 13>5--5>11--11>13)

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

[{1, 13, 5}, {11, 13}, {17, 11, 4, 5}, {17, 4, 1}]

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

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

def core(L):
"""remove singletons from sets

Examples
========

>>> from random import randint
>>> core(d:=[{randint(1,20) for i in range(5)} for i in range(4)])
[{1, 13, 5}, {11, 13}, {17, 11, 4, 5}, {17, 4, 1}]
>>> d
[{1, 5, 6, 13, 19}, {2, 7, 11, 12, 13}, {4, 5, 10, 11, 17}, {16, 17, 4, 1}]
"""
from collections import defaultdict
sets = [set(i) for i in L]
loc = defaultdict(list)
for i in range(len(sets)):
for e in sets[i]:
loc[e].append(i)
return [{i for i in s if len(loc[i]) - 1} for s in sets]

Альтернативная аналогия с визуализацией
Другой способ визуализировать «путь/петлю» — представить цветные точки на сетке: столбцы содержат элементы множества и равные элементы находятся в одной строке. Петля – это путь, который начинается в одной точке и заканчивается в той же точке, перемещаясь по вертикали или горизонтали от точки к точке и должен включать оба направления движения.


Подробнее здесь: https://stackoverflow.com/questions/793 ... st-of-sets