drford
@drford
Прокрастинирую с 1993 года

Как сгенерировать цепь перестановки?

Добрый вечер. Каким образом можно узнать, какие цепи перестановки существуют в рамках перестановки, если даны перестановка и исходная последовательность(оба в виде списка)?
Поясню: цепь перестановки - это такая последовательность а(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
  • Вопрос задан
  • 68 просмотров
Решения вопроса 1
@Drill
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]]
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы