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

Для интуитивного понимания проблемы, я думаю, мы можем использовать эту метафору. Визуализируйте часы на стене, но вместо 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.

немного проще пойти снизу вверх:

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

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

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

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

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

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

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

Отредактируйте для дальнейших размышлений:

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

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

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

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

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

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