Permutations and Combinations
Patrick McAtee, Tom Rice, and Jesse Whidden


Generating Permutations and Combinations

Information on creating permutations and combinations, focusing on generating the next permutation/combinations in lexicographic order.

Introduction

The other parts of this tutorial have provided information about permutations and combinations in general. However, there are times when a certain permutation or combination is needed to solve a specific problem. To find that specific permutation/combination, there has to be a method to generate other arrangements of numbers.

Generating Permutations

Generating the permutations of the n smallest positive integers and then replacing those integers with any set of n elements will create the set of permutations for that set. Often, the permutation of a set will be given in lexicographic ordering.

Definition
The lexicographic ordering for a set of permutations {1,2,3,...,n-1,n} has the permutation a1a2...an precede the permutation b1b2...bn when, for some k, 1 <= k <= n, a1 = b1, a2 = b2, ..., ak-1 = bk-1, and ak < bk.

A procedure for generating the next permutation in lexicographic order can be developed for a given a1a2...an. If an-1 < an, swap the two to get the next largest permutation (..56 to ...65). If an-1 > an, then a larger permutation cannot be made from the two integers. In that case, look at the final three integers. If an-2 < an-1, then put the smaller of the two integers an-1 and an in the an-2 position. Fill the remaining positions in lexicograpic order to complete the permutation (..165 to ...516). This procedure can be generalized to produce the next largest permutation for any a1a2...an. This algorithm is used to generate permutations in the applet below.

Algorithm
Generating the Next Largest Permutation in Lexicographic Order

(Assuming {a1a2...an} is not {n,n-1,...,2,1} ) 

NextPermutation(a1a2...an)
{
    j = n - 1;
    while (a[j] > a [j+1])
    {
          j--;
    }
    k = n;
    while (a[j] > a[k])
    {
          k--;
    }
    Swap(a[j],a[k]);
    r = n;
    s = j + 1;
    while (r > s)
    {
         Swap(a[r],a[s]);
         r--;
         s++;
    }
}

Generating Combinations

For any r-combination, a procedure for creating the next largest combination can be developed. A combination a1a2...ar in lexicographic order is given for a set {1,2,3,...,n}. In the set {1, 2, 3, 4, 5, 6}, a 4-combination could be {1, 2, 5, 6}. To obtain the next largest combination, find the last ai in the combination so that ai != n - r + i. (The last element in the combination with ai != n - r + i is 2.) Replace ai with ai + 1, and aj with aj + j - i + 1, for j = i +1, i + 2, ..., r. (This creates the next largest combination, {1, 3, 4, 5}. This algorithm is also used in the applet below.

Algorithm
Generating the Next Largest r-Combination in Lexicographic Order

(Assuming {a1, a2,..., ar} is not {n-r+1,...,n}, and
ai < aj when i < j ) 

NextCombination(a1a2...ar)
{
    i = r;
    while (a[i] > n - r + i)
    {
          i = i - 1;
    }
    a[i] = a[i] + 1;
    for (j = i + 1; j <= r; j++)
    { 
          a[j] = a[i] + j - i;
    }
}

Generating Permuataions/Combinations Applet Instructions:
Permutations: Enter a permutation that uses all integers from 1 to some n (using each integer only once). Separate each integer with a semicolon (;).
Combinations: Enter a combination in ascending order; separate each integer with a semicolon (;). Then enter an integer for the set size that is equal to or greater than the last integer in the combination.

Source code: NextPermComb.java

Use this applet to do the following problems:

Examples

1.In the set {1, 2, 3, 4, 5}, which permutation is first in lexicographic ordering - 23514 or 23415?

2.What is the next permutation in lexicographic order after 362541?

3.What is the next largest 4-combination in the set {1, 2, 3, 4, 5, 6} after {2, 4, 5, 6}?

Answers

1.The first two positions in those permutations are the same (2 and 3, respectively), but in the third position, one permuatation has a 5 and the other has a 4. Since 4 < 5, 23415 comes first.

2.The last two integers in the set where aj < aj+1 are 2 and 5 (positions a3 and a4 in the permutation). Swap 2 with the number to its right that is the next greatest in size (4). Then place the remaining three integers in lexicographic order to obtain the permutation 364125.

3.The last element in the combination with ai != 6 - 4 + i is a1 = 2. Replace ai with ai + 1, (2 with 3) and 3 with 4, 4 with 5, and 5 with 6. This creates the next largest combination, {3, 4, 5, 6}