Permutations of a given set of numbers

Question

Can someone explain a good algorithm for effectively finding all permutations of a given set of numbers?

Answer 1

The simplest approaches are recursive, i.e. in executable pseudo code,

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]

, [1:] [:1] "" ( ", " " " ), " 0- i- " " " (.. ;-). yield " , ", return " , !".

, , - . , , , , ! -)

Answer 2

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

Answer 3

# Alex:

    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 sorting creates a certain permutation of the data.

Be careful with combinatorial (and permutation) algorithms that find all combinations or permutations. They have very expensive expenses for a Big-O note.