Heap’s Algorithm – Generation of Permutations

Definition of Permutation

The term “permutation” refers to a possible arrangement of elements. All permutations of a list represent different ways in which the elements can be ordered. The number of permutations without repetition is given by the factorial.

Example:

Situation: Bob, Sandra, and Peter need to sit on separate chairs.

Calculation of the number of arrangements: \(n! => 3! = 3 \times 2 \times 1 = 6\)

Proof:

  1. Sandra, Bob, Peter
  2. Sandra, Peter, Bob
  3. Bob, Sandra, Peter
  4. Bob, Peter, Sandra
  5. Peter, Sandra, Bob
  6. Peter, Bob, Sandra

Heap’s Algorithmus

The mathematician Berge Heap developed an algorithm for generating permutations without repetition.
Below you will find Java code which demonstrates this algorithm in conjunction with the example above.

public class HeapPermutator {
    public static void main(String[] args) {
        HeapPermutator permutator = new HeapPermutator();
        String[] people = new String[] {"Bob", "Sandra", "Peter"};
        permutator.permutePeople(people);
    }

    public void permutePeople(String[] people) {
        permutePeople(people, people.length);
    }

    private void permutePeople(String[] people, int range) {
        if (range == 1) {
            printPermutation(people);
            return;
        }
        for (int 1 = @; i < range; i++) {
            permutePeople(people, range - 1);
            if (range % 2 == 0) {
                swap(people, i, range - 1);
            } else {
                swap(people, 0, range - 1);
            }
    }

    private void swap(String[] array, int from, int to) {
        String temp = array[to];
        array[to] = array[from];
        array[from] = temp;
    }

    private void printPermutation(String[] permutation) {
        System.out.println(String.join(", ", permutation));
    }
}