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

[Anonymous]

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

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

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

продукт (1,2,3) будет сгенерирован дважды в itertools.product(*sets), поскольку литералы (1,2,3 ) и (2,3,1), потому что есть цикл. Если петли нет, то и дублирования не будет, даже несмотря на то, что между наборами может быть много общего.
Петля формируется в A в наборе, когда вы путешествуете в B в одном и том же наборе. set, а затем к B в другом наборе, в котором есть A, или к B в другом наборе с C, который соединяется с набором с A. например. 1>2--2>3--3>1, где '--' указывает на перемещение между наборами, а '>' указывает на перемещение внутри набора. Самый маленький цикл будет включать пару чисел, общих для двух наборов, например. а>б--б>а. {edit: обозначение @ravenspoint приятно, я предлагаю использовать {a}-b-{a} вместо приведенного выше.} Циклы в канонической форме не должны иметь связующее значение, используемое более одного раза: либо это представляет собой случай, когда петля повторяется сама по себе (как в курсиве «i») или есть петли меньшего размера, которые можно сделать (например, внешний и внутренний квадраты на Арке де Triumph](https://commons.wikimedia.org/wiki/File ... iomphe.jpg).
Какой тип графической структуры я мог бы использовать, чтобы представить это? каждый набор как узел, а затем указать, какие наборы с какими связаны, но это неправильно, поскольку для [{1,2},{1,3},{1,4}] существует соединение между всеми наборами -- общий 1 - но цикла нет. Я также пытался присвоить букву каждому числу в каждом наборе, но это тоже кажется неправильным, поскольку тогда я не знаю, как различать циклы внутри. набор.
Это было вызвано вопросом о создании уникальных продуктов.
Примерные наборы, подобные следующему (которые имеют тривиальную цикл 4>17--17>4 и более длинные петли, например 13>5--5>11--11>13)

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

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

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

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