[This page is auto-generated; please prefer to read the article’s PDF Form.]
Given an array a of N elements which are all distinct, we want to generate all the N! permutations of its elements. Since N! grows very fast with N (e.g. 15! = 1307674368000), it is generally not practical to store all the permutations in memory. The approach we take is to generate each permutation in array a itself, process it (e.g. print), then generate a new permutation in a, and so on.
R. Sedgewick provided a very good survey about permutation generation algorithms in [1]. In this article, we will discuss a few recursive algorithms for this problem. All of them are based on a common recursive structure which is described below.
We will be denoting any subarray of a from some index i to some index j (j ≥ i) as a[i : j]. All implementation will be in C language, and assumes elements of array a to be of type “int”.
[Next]
Copyright © 2021 Nitin Verma. All rights reserved.