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

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!-)

Answer 2

http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 3

My c# implementation of Alex's pseudocode:

    private int length;
    private List<List<string>> permutations;

    public List<List<string>> Generate(List<string> list)
    {
        length = list.Count;
        permutations = new List<List<string>>();

        foreach(List<string> subperms  in Recursive(list))
            permutations.Add(subperms);

        return permutations;
    }

    private List<List<string>> Recursive(List<string> list)
    {
        List<List<string>> subperms = new List<List<string>>();

        if (list.Count <= 1)
        {
            subperms.Add(list);
            return subperms;
        }

        for (int i = 0; i < list.Count; i++)
        {
            string temp = list[0];
            list[0] = list[i];
            list[i] = temp;

            List<string> tail = new List<string>(list);
            tail.RemoveAt(0);

            List<string> head = new List<string>();
            head.Add(list[0]);

            foreach (List<string> subperm in Recursive(tail))
            {
                List<string> headCopy = new List<string>(head);
                headCopy.AddRange(subperm);

                if (headCopy.Count == length)
                    permutations.Add(headCopy);
                else
                    subperms.Add(headCopy);
            }

            temp = list[0];
            list[0] = list[i];
            list[i] = temp;
        }

        return subperms;
    }

Answer 4

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.