[This page is auto-generated; please prefer to read the article’s PDF Form.]
Given an array a of N distinct elements, we want to write a program to generate all permutations of the N elements. There will be N! such permutations.
As N! is very large even for small N, we will never want to store all the generated permutations in memory. So, we can process each permutation as soon as it is generated, before constructing another permutation.
In mathematical expressions, ai will be used to represent element a[i] of the array a. Since contents of array a may change during such a program, we will refer to the initial sequence of elements in array a, (a0,a1,a2,…,aN−1), as elements (A0,A1,A2,…,AN−1).
If an algorithm needs to generate all possible permutations of N elements, it should not generate one permutation after other in random order. Because, then it has no efficient way to remember which permutation it has already generated and which ones are remaining. The algorithm needs to generate them in a definite order: the ith permutation generated is definite for a given input. An algorithm to generate permutations has this order defined, and provides a method to generate permutations in that order.
In this article, we discuss an algorithm which generates permutations in Lexicographical Order. The algorithm has been discovered multiple times independently, but is known to be first published in 1812 by L. L. Fischer and K. C. Krause [1]. So, it is sometimes referred as Fischer-Krause Algorithm.
[Next]
Copyright © 2021 Nitin Verma. All rights reserved.