Алгоритмы Python: генерация ожерелья / круговые перестановки

Когда у вас есть список из N элементов, одна из циклических перестановок списка однозначно задается его первым элементом. Это означает, что у вас будет ровно N циклических перестановок (включая исходный список), и вы можете переходить от одного к другому, удаляя первый элемент и добавляя его в конец списка.

Вы можете легко создать генератор для всех циклических перестановок списка:

def circ_perm(lst):
    cpy = lst[:]                 # take a copy because a list is a mutable object
    yield cpy
    for i in range(len(lst) - 1):
        cpy = cpy[1:] + [cpy[0]]
        yield cpy

Демо:

>>> list(circ_perm([1,2,3,4]))
[[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

Если вам нужны уникальные перестановки, когда две перестановки являются круговой перестановкой другого, вы все равно можете использовать тот факт, что круговая перестановка задается его первым элементом, и исправить первый элемент и найти все перестановки того, что осталось. :

def uniq_perm(lst):
    gen = itertools.permutations(lst[1:])
    for end in gen:
        yield [lst[0]] + list(end)

Демо:

>>> list(uniq_perm([1,2,3,4]))
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]

Сложность выполнения перестановки составляет около O (n * n!), Поэтому для большого числа или списка было бы неэффективно генерировать все возможные перестановки. Вы можете использовать отслеживание с возвратом для создания перестановки списка, я поделюсь ссылкой, может быть, это поможет . Решение основано на возврате

   
def permute(a, l, r):
    if l == r:
        print(a)
    else:
        for i in range(l, r + 1):
            a[l], a[i] = a[i], a[l]
            permute(a, l + 1, r)
            a[l], a[i] = a[i], a[l]

data = [1,2,3,4,5]
n = len(data)
a = list(data)
permute(a, 0, n - 1)

Следующий код производит все перестановки последних чисел n-1, добавляя к каждой перестановке первый элемент исходного списка.

from itertools import permutations
circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]

Где my_list - ваш начальный список значений для генерации всех циклических перестановок.

1. Подумайте о «неподвижной точке» ожерелья.
2. позаботьтесь о том, чтобы бусинка с наименьшим номером, 1, была повернута в эту точку
3. Тогда только заказы бисера это все перестановки элементов, начинающиеся с 1

Поскольку генератор itertool.permutations в Python имеет первый элемент во входном списке, наименее изменяющийся при последовательном выходе, следующий код просто выводит все решения, как видно при повороте на фиксированную точку выше.

   
from itertools import permutations, islice
from math import factorial

items = [1, 2, 3 ,4]
ilength = len(items)
base_necklace_orders = list(islice(permutations(items), factorial(ilength) // ilength))
print(base_necklace_orders)
# [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2)]

Есть две библиотеки Python (о которых я знаю), которые будут генерировать комбинаторные ожерелья. Это мудрец и SymPy.