Permutations with repetitions

Permutations are all the different orders of the elements of a set. The number of permutations is n! (n factorial), where n is the number of elements of the set. If there are repeated elements in the set to permute, the number of permutations will be smaller. I have compiled some methods in Java to obtain all the permutations with repetitions.

Contents
Introduction
Permutations with repetitions
References

Introduction

The number of permutations of a set of elements with n elements is n! (n factorial). If there are repeated elements in the set, we will have to divide by the factorial of the number of repetitions of each repeated element.

REF: "Permutaciones con repetición"

The number of permutations with repetition of n elements, with groups of k elements because of repetitions (where k = r₁ + r₂ + ...+ r_n), written as P_k^r1,r2...rn and equal to:

Pkr1,r2...rn =

n! r1!r2! ... rn!

Permutations with repetitions

Based on the permutations generator algorithms, the following methods generate the permutations for a set with repetition:
1. The set is sorted.
2. When there are to permute, they consider if the elements are equal or no.

permutationsRep(int[]) (recursive)

/** 
 * Given ps, integer set with repetitions, it sorts it, and
 * calls the method to permute it.
 *
 * @param ps Array of integers with repetitions, set of 
 * elements to permute.
 */
public void permutationsRep(int[] ps) {
    Arrays.sort(ps);
    permuteRep(ps, 0, ps.length);
}
  
/** 
 * Calls doSomething() method with all the permutations
 * of the ps set.
 *
 * It considers when elements are repeated.
 *
 * Initial call: permute(ps, 0, ps.length);
 *
 * @param ps Array of integers with repetitions, set of 
 * elements to permute.
 * @param start Index where permutation begins.
 * @param n Number of elements of ps.
 */
public static void permute(int[] ps, int start, int n) {
    doSomething(ps);
    int tmp = 0;

    if (start < n) {
      for (int i = n - 2; i >= start; i--) {
        for (int j = i + 1; j < n; j++) {
          if (ps[i] != ps[j]) {
            // swap ps[i] <--> ps[j]
            tmp = ps[i];
            ps[i] = ps[j];
            ps[j] = tmp;

            permute(ps, i + 1, n);
          }
        }

        // Undo all modifications done by
        // recursive calls and swapping
        tmp = ps[i];
        for (int k = i; k < n - 1;)
          ps[k] = ps[++k];
        ps[n - 1] = tmp;
      }
    }
  }

permuteRepIteretive(int[]) (iterative)

/**
* Calls the doSomething() method with all the permutaions
* of ps.
*
* It considers when elements are repeated.
*
* @param ps Array of integers with repetitions, set of
* elements to permute.
*/
public void permuteRepIteretive(int[] ps) {
   doSomething(ps);
   int n = ps.length;
   int tmp = 0;

   // indexes[i] = i+1;
   int[] indexes = new int[n];
   for (int i=0; i<n-1; ) indexes[i] = ++i;

   for (int i = n-2; i >= 0;) {
  
     while(indexes[i]<n && ps[indexes[i]] == ps[i]) {
       indexes[i]++;
     }
    
     // swap ps[i] <--> ps[indexes[i]
     if (indexes[i]<n) {
       tmp = ps[indexes[i]];
       ps[indexes[i]] = ps[i];
       ps[i] = tmp;
      
       doSomething(ps);
     }
    
     indexes[i]++;     

     i = n-2;

     while (i >= 0 && indexes[i] >= n) {
       // Undo previous permutation from i+1
       // Cyclical rotation to the left from i+1
       // ps[k] = ps[k+1]
       tmp = ps[i];
       for (int k = i; k < n-1;)
         ps[k] = ps[++k];
       ps[n-1] = tmp;

       // indexes[i]=i+1;
       // i--;
       indexes[i] = i-- + 1;
     }
   }
 }

References

"Counting problems", by Johan.Claeys.
"Permutaciones con repetición".