Алгоритм генерации множеств с повторениями

[serega]

Добрый день.
Скажите, пожалуйста, где можно посмотреть/прочитать про такой алгоритм?
Читал Липского "Комбинаторика для программистов", нашел только перестановки в наборе и генерацию бинарного множества с повторениями.
Не понимаю, как последний "рецепт" адаптировать под свою задачу. К сожалению, у меня очень слабый математический бэкграунд.

Есть набор элементов: 1,2,3. Надо сгенерировать все возможные последовательности длиной 4, используя заданный набор эл-тов.
1111
1211
1121
1112
2111
2211
...
3333

Кстати, а возможно ли такие последовательности генерировать в несколько потоков?
По идее, можно.

Где смотреть, куда копать? Есть ли книжка, где рассматриваются подобные задачи? Липский для меня пока что неподъемен, слишком сложно и слишком мало знаю, комбинаторики в универе вообще не было.


Спасибо!

[maxal]

serega в сообщении #305309 писал(а):

Где смотреть, куда копать? Есть ли книжка, где рассматриваются подобные задачи?

А. Шень. Программирование: теоремы и задачи. 2-е изд., М.: МЦНМО, 2004, 296 с.
ftp://ftp.mccme.ru/users/shen/progbook2/progbookpdf.zip

[serega]

Мне такая книга две недели назад с Амазона приехала, правда, на английском языке.
Открываю русский вариант и ощущаю дежавю. Я только первую главу успел прочитать.
Спасибо.

[Circiter]

2serega

Цитата:

Есть набор элементов: 1,2,3. Надо сгенерировать все возможные последовательности длиной 4, используя заданный набор эл-тов.

Можно обойтись и без знания комбинаторики. Достаточно заметить, что искомые последовательности суть числа над данным алфавитом (в вашем примере над "цифрами" 1, 2, 3).

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

Можно понимать этот алгоритм и так. Если обозначить ваш алфавит как $\Sigma$, то искомые последовательности фиксированной длины $n$ будут, по-сути, просто элементами декартовой степени $\Sigma^n$. И, как вы понимаете, при маленьком статически заданном $n$ можно даже просто обойтись набором вложенных циклов, e.g.:

Используется синтаксис C

    for(i=1; i<=3; i++)
        for(j=1; j<=3; j++)
            ...
                printf("%d%d...", i, j, ...);
 

N.B., "цифрами" могут быть любые различимые объекты.

Цитата:

Кстати, а возможно ли такие последовательности генерировать в несколько потоков?

Да.