Permutations
This program displays all possible permutations of n data items.
Programming Issues
The algorithm used is fairly simple. For each item i in a set of n items:
- Remove item i from the data set;
- Find all permutations of the remaining n - 1 items;
- Insert item i back into the set in its original position
The recursive function Perm() shows this algorithm.
Each permutation is printed as it is found.
The rest of the code is relatively lengthy, but merely supports the above algorithm by providing it with appropriate data structures. Two data structures are provided:
- A data set, an ordered list allowing two operations:
- Removing an item from a given position, and
- Inserting an item into a given position
- A stack to hold the current permutation, which like
all stacks allows two operations:
- Pushing an item onto the top of the stack, and
- Popping an item off the top of the stack
In order to understand the algorithm used to find the permutations,
it is not necessary to delve into the details of these functions
or data structures any more than it is necessary to understand exactly
how a printf() call produces output on your screen. The
main() and Perm() functions describe the
algorithm completely. To demonstrate this, two versions of the program
are supplied, one using linked lists, and one using arrays. Aside from
the files data_####.c and stack_####.c the
two versions are identical.
Functions to:
- Initialize and free memory used by the data set,
- Print out the contents of the stack, and
- Retrieve the number of data items from the command line
are also provided.
Some performance statistics for this example are available.
Usage
Pass the number of data items to the command line as the single argument. An example session is shown below:
[paul@hermes perm]$ ./perm 3
Permutations of 3 items:
ABC
ACB
BAC
BCA
CAB
CBA
6 permutations in all.