Permutations of a given set of numbers [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question 开发者_运维知识库

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

---

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

---

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

---

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;
    }

---

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.