Найти все мультимножества для перестановок набора данных

Question

У меня есть набор данных в php с 7 элементами, для простоты мы можем предположить, что это следующее:

$S = array("A", "B", "C", "D", "E", "F", "G");

Я пытаюсь создать список всех мультимножеств в S для переменного (определяемого) количества элементов в мультимножестве.

Например, если бы я хотел все мультимножества с 2 элементами, он бы вывел следующее (опуская кавычки для простоты):

{(A,A),(A,B),(A,C),(A,D),(A,E),(A,F),(A,G),(B,B),(B,C),(B,D),
    (B,E),(B,F),(B,G),(C,C),(C,D),(C,E),(C,F),(C,G),(D,D),(D,E),
    (D,F),(D,G),(E,E),(E,F),(E,G),(F,F),(F,G),(G,G)}

Я знаю формулу множественного выбора, чтобы найти число мультимножеств [a,b] = [n-1,k] for (a+b)!/(a!b!), но не знаю, как создать собственно мультимножества.

Answer 1

Чтобы перечислить n с множественным выбором k, перечислите n+k-1, выберите k, а затем уменьшите позицию i результата на i (индексирование от 0).

Например, чтобы перечислить 3 с множественным выбором 3, перечислите 5, выберите 3 и сопоставьте

012 -> 000
013 -> 001
014 -> 002
023 -> 011
024 -> 012
034 -> 022
123 -> 111
124 -> 112
134 -> 122
234 -> 222.