Algorithm of the day -

Heap's Algorithm

Summary

Heap's Algorithm is a method for generating all permutations of a given set of elements. It is a recursive algorithm that uses a clever technique to avoid generating duplicate permutations.

Use Case

Heap's Algorithm can be used to generate all possible orderings of a deck of cards. This can be useful in card games where the order of the cards matters.

Steps

  1. Start with the initial permutation of the elements.
  2. If the length of the permutation is 1, return the permutation.
  3. For each element in the permutation, swap it with the last element.
  4. Generate all permutations of the remaining elements.
  5. Swap the last element back to its original position.
  6. Repeat steps 3-5 until all elements have been swapped.

Complexity

The time complexity of Heap's Algorithm is O(n!), where n is the number of elements in the permutation. The space complexity is O(n), as we need to store the current permutation.

Code Example

def heap_permute(data, n):
    if n == 1:
        print(data)
    else:
        for i in range(n):
            heap_permute(data, n - 1)
            if n % 2 == 1:
                data[0], data[n - 1] = data[n - 1], data[0]
            else:
                data[i], data[n - 1] = data[n - 1], data[i]

data = [1, 2, 3]
heap_permute(data, len(data))