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

Question

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

Для мультимножества A пусть P (A) обозначает множество всех возможных перестановок A. P (A) естественно делится на непересекающиеся подмножества, которые эквивалентныклассы с отношением эквивалентности «могут быть связаны круговыми сдвигами».Перечислите все эти классы эквивалентности, генерируя ровно по одному члену от каждого из них.

Например, рассмотрим мультимножество {0, 1, 1, 2}.Перестановки «0112» и «1201» являются уникальными перестановками, но последние могут быть найдены путем смещения по кругу первого и наоборот.Желаемый алгоритм не должен генерировать оба.

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

Любое понимание этой проблемы высоко ценится.

Answer 1

алгоритм Савады

Answer 2

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

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

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

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

РЕДАКТИРОВАТЬ: я знаю, что я как бы игнорировал тот факт, что A может содержать дубликаты элементов, но все еще думаю об этой части:)

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

Answer 3

Я предлагаю решение, реализованное на 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 алгоритм дает:

['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']

Answer 4

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

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

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

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

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

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

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

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

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

Answer 5

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

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

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

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

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

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

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