Algorithm X.1: All permutations

Input: a list of $n$ unique objects.
Output: a list of all permutations of those $n$ objects.

Given a collection of unique objects, describe an algorithm that iterates through all possible permutations of those objects.

For example, given ${a, b, c, d}$, describe an algorithm that creates the $4! = 24$ permutations:

	a, b, c, d
	a, b, d, c
	a, c, b, d
	a, c, d, b
	a, d, b, c
	a, d, c, b
	b, a, c, d
	b, a, d, c
	b, c, a, d
	b, c, d, a
	b, d, a, c
	b, d, c, a
	c, a, b, d
	c, a, d, b
	c, b, a, d
	c, b, d, a
	c, d, a, b
	c, d, b, a
	d, a, b, c
	d, a, c, b
	d, b, a, c
	d, b, c, a
	d, c, a, b
	d, c, b, a

You can read more about this problem at Wikipedia and Steven Skiena's algorithm repository.

You can read about:

• Heap's algorithm, and
• the Steinhaus-Johnson-Trotter algorithm

which describe algorithms for finding solutions to this problem.