There is a function like next_permutation, but for permutations with repetition?

Question

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

eg.

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

that I want to return a function:

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

Is there a function that can do this?

Thanks in advance, Erik

Answer 1

You are not performing a permutation, but simply counting.

Ex. if your enumerated set {0, 1} is more than 3 digits, you will receive:

 000 001 010 011 100 101 110 111 

Look, this is just a binary count.

So, match your element set with n-digit numbers, then make an n-based count, which will give you the correct awnser

Answer 2

I wrote this in Java. Not optimized code, but you understand:

 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

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

• First set the first permutation as 1 1 1 .... (k times).

• Find the rightmost index (say j) so that the element in this index is less than k.

• The increment of the element value at index j by one and from the 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 in position 2 (counting the index 0) we have 1 <3, so increase it and reset all the elements after that by 1. The second permutation → 1 1 2.

Then in position 1 (counting the index 0) we have 1 <3, so increase it and reset all the elements after that to 1. Third permutation → 1 2 1

Etc.