## Permutations

Combinations are selections that disregard order. The powerset

*P(S)*of a set S is the set of all possible combinations of the*n*elements of*S*. There are*2*of these. Permutations are arrangements of sequences into orders. The number of permutations of a set is denoted^{n}*n!*For example, the set*{x, y, z}*has*6*permutations :*{x, y, z}, {x, z, y}, {y, x, z}, {y, z, x}, {z, y, x}*and*{z, x, y}*. Suppose*f*exists that for given*k*provides all permutations of*S*that start with*s*. All permutations could then be found by_{k}*f*with*k*ranging over*[0, N - 1]*. But*f*trivially exists as it can be computed by prepending*s*to the permutations of the smaller set_{k}*S - { s*. Here are two programs to compute the permutations of a set based on this idea._{k}}