Добрый вечер. Каким образом можно узнать, какие цепи перестановки существуют в рамках перестановки, если даны перестановка и исходная последовательность(оба в виде списка)?
Поясню: цепь перестановки - это такая последовательность а(n), для которой выполнено:
A'[a(n+1)] = B'[а(n)], где A' - последовательность, состоящая из N первых натуральных чисел, начиная с нуля (0,1,2,3...,N), B' - некоторая перестановка элементов этой последовательности. Число членов в цепи перестановки конечно. Каждый член цепи перестановки является членом последовательности А'.
Пример:
Исходная последовательность: A' [0,1,2,3,4,5,6]
Перестановка: B' [ 2,6,0,5,1,3,4]
Цепи: [1,4,6,1]
[0,2,0]
Идеи такие: берём A'[0], ищем индекс элемента с таким значением в B'. Этот индекс - 2. Далее ищем индекс двойки в A'. Это 0. Цепь замкнулась, получилось 0 2 0
Выкидываем из исходной последовательности все элементы цепи. Имеем:
А' = [1,3,4,5,6]
А'[0] =1
Ищем в В' единичку. Она у нас под номером 4. Потом ищем индекс четверки в В', это 6. Потом ищем индекс шестерки в B', получается 1. Но 1 уже есть в цепи перестановки, следовательно, цепь замкнулась. Имеем цепь 1 4 6 1
A = [0,1,2,3,4,5,6]
B = [2,6,0,5,1,3,4]
def chains(a,b):
chain, list_chains = [a[0]], []
while a:
chain += [b.index(chain[-1])]
if chain[0] == chain[-1]:
list_chains += [chain]
a = [i for i in a if i not in chain]
if a:
chain = [a[0]]
return list_chains
print(chains(A,B))
In [3]:
[[0, 2, 0], [1, 4, 6, 1], [3, 5, 3]]
