Эффективный алгоритм получения перестановок с повторениями

[maximkarimov]

Известно, что количество перестановок с повторениями равно частному от деления факториала количества элементов на произведение факториалов коэффициентов повторения элементов. Также известны несколько эффективных алгоритмов получения перестановок с повторениями - они генерируют матрицу, каждая строка которой сразу является уникальной перестановкой (удается избежать построения, а значит и последующего отсева тождественных строк).
Однако, матрица перестановок с повторениями содержит множество строк, которые совпадают друг с другом при циклическом сдвиге - подобно тому, как совпадает с самим собой ожерелье при вращении. Например, для множества элементов [2 2 2 2 3] матрица уникальных перестановок содержит 5 строк и все они отличаются лишь циклическим сдвигом. Если определить, что две перестановки, которые отличаются лишь циклическим сдвигом, являются тождественными, то естественным образом возникают следующие вопросы, которые и предлагается обсудить:
1. Каково количество уникальных перестановок с повторениями, если две перестановки отличающиеся лишь циклическим сдвигом рассматриваются как тождественные?
2. Какова может быть принципиальная схема эффективного алгоритма генерации множества таких уникальных перестановок с повторениями?

[tolstopuz]

http://www.cis.uoguelph.ca/~sawada/papers/alph.pdf

[maximkarimov]

Это просто великолепно! Нет слов. Я упустил из виду, что вопрос можно свести именно к эффективному алгоритму генерации бинарных ожерелий. Формула для вычисления их количества также известна. Огромное спасибо!

[maximkarimov]

tolstopuz в сообщении #1457548 писал(а):

http://www.cis.uoguelph.ca/~sawada/papers/alph.pdf

Досадно, что ссылка на с-код в конце статьи нерабочая. Придется разбираться.

[tolstopuz]

Вот эта вроде работает.

http://www.cis.uoguelph.ca/~sawada/programs.html

[maximkarimov]

Да, работает! Спасибо огромное!