Кодирование перестановок с повторяющимися значениями

Question

Я пытаюсь сгенерировать все комбинации A, B, C, D, E в трех положениях:

A,A,A
A,A,B
C,A,E
C,B,A
C,B,B
etc...

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

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

Кроме того, как это называется и как я могу узнать больше о вариациях в подходах? Некоторые похожие решения, которые я видел, генерируют только неповторяющиеся комбинации (ABC, ABD), другие не используют значения повторно.

Мое предположение, основанное на моем прошлом подходе к рекурсии, заключается в том, что permutation(0) приведет к aaa, а permutation(100) приведет к adw.

Answer 1

Определенные комбинации, которые вы ищете, кажутся просто «любой из A, B, C, D, E в каждой позиции». В этом случае они очень похожи на «пятидесятник» (база 5) позиционная система счисления : у вас есть три цифры, и каждая из них может независимо быть 0 (A), 1 (B), 2 ( C), 3 (D) или 4 (E). То же самое касается кодирования их как целых чисел: просто пронумеруйте их от 0 до 5 ³ -1.

Для числа k «комбинация» есть «(k div 5 ² ) mod 5, (k div 5 ¹ ) mod 5, (k div 5 * 1011» * 0 ) мод 5, с ABCDE, закодированным как 01234, соответственно.

Для "комбинации", такой как "xyz", сначала сопоставьте буквы ABCDE с цифрами 01234 как x, y и z, а затем кодовое число x * 5 ² + y * 5 ¹ + z * 5 ⁰ .