Есть ли алгоритм для генерации всех уникальных циклических перестановок мультимножества?

Ответ 1

алгоритм Sawada

Ответ 2

немного легче перейти на этот снизу вверх:

если A содержит только один элемент, P (A) также содержит одну перестановку. легко увидеть те же самые работы, если A содержит только 2 элемента.

Теперь предположим, что у вас уже есть все P (A) для A с n элементами, и вы добавляете один элемент. он может находиться в любом из n пятен в любой из перестановок в P (A).

Я думаю, что эта идея очень хорошо переводится на рекурсивный алгоритм на выбранном вами языке и надеюсь, что мои объяснения будут достаточно ясными.

EDIT: Я знаю, что я проигнорировал тот факт, что A может содержать повторяющиеся элементы, но все же думать об этой части:)

так же, как если бы - если вы отсортировали A перед запуском алгоритма перестановки, я думаю, что это может устранить дубликаты. (все еще думая об этом)

Ответ 3

Для интуитивного понимания проблемы я думаю, что мы можем использовать эту метафору. Визуализируйте часы на стене, но вместо того, чтобы иметь 12 позиций на лице, оно имеет n, где n - количество элементов в вашем наборе.

Тогда каждый класс эквивалентности представляет собой просто назначение элемента A в положение на циферблате.

После присвоения другой перестановки из того же класса эквивалентности может быть сгенерирован простым вращением часов на стене.

Чтобы создать другую несвязанную перестановку A, вам нужно, чтобы элемент пропускал хотя бы один другой элемент.

Теперь алгоритм, который, как я вижу, должен начинаться с задания, например, сказал, что у нас было четыре элемента в = {a, b, c, d}, и мы назначили их в позиции 12, 3, 6 и 9 соответственно для визуальной ясности. Тогда наша первая операция заключалась бы в замене a и b. то a и c, то a и d, тогда мы перейдем к b и поменяем его на элемент в 3-положении, которое теперь является c.

Выполняя это до тех пор, пока мы не достигнем d, будем генерировать представителя из всех классов эквивалентности.

Это не заботится о дубликатах, но должно быть гораздо более эффективным, чем генерация всех перестановок A.

Ответ 4

Мысль, которая приходит мне в голову, состоит в том, что для любого набора, имеющего хотя бы один элемент, который появляется только один раз, вы можете поместить этот элемент в первую позицию своего списка для всех ответов и затем сгенерировать все перестановки остальных цифры. Это довольно тривиальное решение, поскольку тот факт, что ваш первый элемент уникален, гарантирует отсутствие эквивалентов при циклическом перемещении элементов. Очевидно, что все созданные вами решения должны быть уникальными.

Очевидная проблема заключается в том, что если у вас нет элементов, которые являются синглами, то это полностью разрушается. Основная причина, по которой я заключаю это, состоит в том, что существует несколько других решений, не имеющих дубликатов, и я думаю, что этот более эффективен, чем они (решает больше случаев), поэтому стоит упомянуть. Его также довольно просто с точки зрения понимания того, как он работает и реализует его. Я просто надеюсь, что мои рассуждения звучат.; -)

Изменить дальнейшие мысли:

Мне кажется, что этот принцип можно распространить на ситуацию, когда у вас есть дубликаты в определенной степени.

Если вы возьмете один элемент (который, как мы предполагаем, теперь повторяемся), вы можете посмотреть только на его перестановки и какие из них позволят повторить чередование циклов, как и до предположения, что вы можете "заблокировать" один на своем месте без потери общности. например, если у вас есть в общей сложности 6 элементов, и A появляется дважды в этом наборе, тогда вы можете:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

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

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

Я не уверен на 100%, как вы могли бы сделать это в полностью работоспособной программе, но несколько о том, как избежать необходимости перебора.

Ответ 5

Я предлагаю здесь решение, реализованное в python

import itertools as it

L = ['a','b','c','d']
B = it.combinations(L,2)
swaplist = [e for e in B]
print 'List of elements to permute:' 
print swaplist
print
unique_necklaces = []
unique_necklaces.append(L)
for pair in swaplist:
    necklace = list(L)
    e1 = pair[0]
    e2 = pair[1]
    indexe1 = L.index(e1)
    indexe2 = L.index(e2)
    #swap
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1]
    unique_necklaces.append(necklace)

for n in unique_necklaces:
    # Commented code display the rotation of the elements in each necklace
    print 'Necklaces'
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)]   

Идея состоит в том, чтобы строить разные ожерелья с помощью перестановок из двух элементов. Для списка из четырех элементов a, b, c, d в algo получаем:

['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'c', 'a']
['a', 'c', 'b', 'd']
['a', 'd', 'c', 'b']
['a', 'b', 'd', 'c']