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

Question

Что я хочу сделать, это найти каждую перестановку массива 1-d с повторениями его содержимого.

например.

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... 

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

Спасибо заранее, Erik

Answer 1

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

Ex. если ваш Enumerating множество {0, 1} более 3 цифр, вы получите:

000 
001 
010 
011 
100 
101 
110 
111 

Престола, это просто бинарный подсчет.

Так карта ваш элемент установлен в п-цифр, то не п на основе подсчета даст вам право awnser

Answer 2

я это написал в Java.
Non оптимизированного кода, но вы получите точку:

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); 
    } 

} 

Answer 3

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

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

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

3. Приращение значение элемента с индексом J на ​​единицу, и из положения J + 1 K сбросить все элементы к 1.

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

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

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

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

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

И так далее.