Есть ли такая функция, как next_permutation, но для перестановок с повторением?

Question

Я хочу найти каждую перестановку 1-го массива с повторениями его содержимого.

например,

int array[]={1,2,3};
for(i=0;i<3;i++){
    next_permutation(array,array+3)
    for(int j=0;j<=3;j++){
        printf("%d ",array[j]);
    }
printf("\n");
}

вернет:

1 2 3
1 3 2
2 1 3
etc...

что я хочу, чтобы функция возвращала:

1 1 1
1 1 2
1 2 1
2 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
etc...

Есть ли функция, которая может сделать это?

Заранее спасибо, Эрик

Answer 1

Вы не делаете перестановку, а просто считаете.

Пример.если ваш перечисляющий набор {0, 1} состоит из 3 цифр, вы получите:

000
001
010
011
100
101
110
111

Видите, это просто двоичный счет.

Итак, отобразите ваш набор элементов в n цифртогда делать n -ный подсчет даст вам правильный awnser

Answer 2

Обычно при вычислении перестановок целых чисел от 1 до k (с повторением):

1. Первоначально установить первую перестановку как 1 1 1 .... (k раз).

2. Найдите самый правый индекс (скажем, j), чтобы элемент с этим индексом был меньше k.

3. Увеличивает значение элемента с индексом j на единицу, а с позиции j + 1 до k сбрасывает все элементы до 1.

4. Повторите шаги 2 и 3.

Применяя эту логику, мы теперь получаем:

1-я перестановка -> 1 1 1.

Затем в позиции 2 (отсчет 0 индекса) мы имеем 1 <3, поэтому увеличиваем его и сбрасываем все элементы после этого до 1. 2-я перестановка -> 1 1 2.

Тогда в позиции 1 (отсчет 0 индекса) у нас есть 1 <3, поэтому увеличиваем его и сбрасываем все элементы после этого до 1. 3-я перестановка -> 1 2 1

и т. Д.

Answer 3

Я написал это на Java.
Неоптимизированный код, но вы понимаете:

String [] data = {"1","2","3"};
public void perm(int maxLength, StringBuffer crtComb){

    if (crtComb.length() == maxLength){
        System.out.println(crtComb.toString());
        return;
    }

    for (int i=0; i<data.length; i++){
        crtComb.append(data[i]);
        perm(maxLength, crtComb);
        crtComb.setLength(crtComb.length()-1);
    }

}