Listing all permutations of a given set of values

Question

I am interested in comparisons of different techniques/approaches one could use to generate all potential permutations of a given set.

Answer 1

You can choose between performance, particular distribution and simplicity. By a particular distribution I mean, whether you care about some particular order, such as lexicographic, of the output.

The best performing algorithm to my knowledge is the Steinhaus algorithm. It is optimal up to a multiplicative constant in the sense that only a constant number of processor instructions are necessary to generate one permutation (not counting the instructions necessary to print it out which is not always needed).

There is also a very simple algorithm that produces the permutations in the lexicographic order that you will probably be able to reinvent as a recursive procedure yourself, and whose performance is O(n.log(n).log(n)), therefore roughly the same as generating the list by any other method and sorting it.

Edit: here is pseudocode of the simple algorithm:

void permute(Element[] permutationPrefix, Set rest)
{
    if (rest.IsEmpty) {
        // permutationPrefix is now a full permutation
        print(permutationPrefix);
    } else {
        foreach (element in rest) {
            permutationPrefix.Append(element);
            permute(permutationPrefix, rest.Minus(element))
            permutationPrefix.Length--;  // cut away the last item
        }
    }
}

Initially call this with an empty permutationPrefix and rest holding the full set; if this set is a sorted data structure, the permutations will be output in the lexicographic order.

Note that we are copying and modifying the set at each recursive call, which is the most expensive operation of the whole algorithm, possibly together with the print method. The cost of a single set copy is logarithmic in the total number of permutations n; and because the depth of the recursive call stack is also logarithmic, the O(n.log(n).log(n)) performance estimate follows.

(This algorithm is also suitable for conversion into a well behaved random permutation generator.)

Answer 2

This question has already been asked and answered (many times in fact):

Algorithm to generate all possible permutations of a list?

Permutations with a given integer

Personally I think the Steinhaus algorithm is over-thinking the problem: it's not much faster than the most naive implementation.

Java-like pseudo-code of the most naive implementation:

List<List<Element>> generateAllPermutations(List<Element> input)
{
    List<Element> output = new ArrayList<Element>();
    if (input.size() == 0)
        return output;
    for (Element first : input) {
        for (List<Element> sequence : generateAllPermutations(input - first))
            output.add(first + sequence);
    }
}