Permutations of a given set of numbers

Question

Can someone please explain a good algorithm to find all permutations of a given set of numbers in an efficient manner?

Answer 1

http://en.wikipedia.org/wiki/Permutation#Algorithms%5Fto%5Fgenerate%5Fpermutations

Answer 2

Have you looked at Knuth 'The Art of Computer Programming'? Volume 3, Sorting and Searching covers it, which makes sense since a sort creates a particular permutation of the data.

Be wary of combinatorial (and permutational) algorithms that find all combinations or permutations. They have very expensive Big-O notation costs.

Answer 3

The simplest approaches are the recursive ones, i.e., in executable pseudocode;

def permute(theseq):
  if len(theseq) <= 1:
    yield theseq
    return
  for i in range(len(theseq)):
    theseq[0], theseq[i] = theseq[i], theseq[0]
    for subperm in permute(theseq[1:]):
      yield theseq[:1] + subperm
    theseq[0], theseq[i] = theseq[i], theseq[0]

in case you're not familiar with executable pseudocode, the notations [1:] and [:1] are meant to denote "slices" (respecively "all but the first" and "just the first"), and the two identical assignments performs the tasks of "swap the 0th and ith items" and "put them back in place" (i.e. swap them again;-). yield means "provide this result but be ready to continue when iterated on", while return means "we're all done, bye bye!".

There are somewhat better approaches along different axes of performance, but the first milestone is making sure you're totally familiar with the fundamental recursive approach and understand it thoroughly -- so I'm stopping here for now. If and when you do fully understand this approach, why it woks just fine and dandy, and how and why it doesn't really seem optimal in performance, I'll be happy to expand on this answer!-)