Is there a function like next_permutation but for permutations with repetition?

Question

What I want to do is to find every permutation of a 1-d array with repetitions of its contents.

e.g.

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

will return:

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

what I want the function to return:

Is there a function that can do that?

Thanks in advance, Erik

This is relevant: http://stackoverflow.com/questions/1944508/arbitrary-digit-counter — Aziz, Mar 24 '12 at 18:06
and this too: http://stackoverflow.com/questions/2380962/generate-all-combinations-of-arbitrary-alphabet-up-to-arbitrary-length — Aziz, Mar 24 '12 at 18:08

score 7 · Accepted Answer · answered Mar 24 '12 at 18:16

You are not doing permutation but just counting.

Ex. if your enumerating set {0, 1} over 3 digits, you'll get:

See, that's just binary counting.

So map your element set into n-digits, then do n-based count will give you the right awnser

score 0 · Answer 2 · answered Oct 03 '14 at 15:49

In general when computing permutations of integers from 1 to k (with repetition):

Initially set first permutation as 1 1 1 .... (k times).
Find the rightmost index (say j) such that the element at that index is less than k.
Increment the value of the element at index j by one, and from position j + 1 to k reset all elements to 1.
Repeat steps 2 and 3.

Applying this logic, we now get:

1st permutation -> 1 1 1.

Then at position 2 (0 index counting), we have 1 < 3, so increment it and reset all elements after this to 1. 2nd permutation -> 1 1 2.

Then at position 1 (0 index counting), we have 1 < 3, so increment it and reset all elements after this to 1. 3rd permutation -> 1 2 1

And so on.

score 0 · Answer 3 · answered Mar 24 '12 at 20:04

I had this written in Java.
Non optimized code, but you get the point:

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

}

Is there a function like next_permutation but for permutations with repetition?

3 Answers3