Algorithm to generate all possible permutations of a list?

Question

Say I have a list of n elements, I know there are n! possible ways to order these elements. What is an algorithm to generate all possible orderings of this list? Example, I have list [a, b, c]. The algorithm would return [[a, b, c], [a, c, b,], [b, a, c], [b, c, a], [c, a, b], [c, b, a]].

I'm reading this here http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

But Wikipedia has never been good at explaining. I don't understand much of it.

Answer 1

Basically, for each element from left to right, you generate all the permutations of the remaining elements. You can do this recursively, (or iteratively if you like pain) until you get to the last element at which point there is only one possible order.

So, given a list: [1,2,3,4]

You just generate all permutations that start with 1, then all the permutations that start with 2, then with 3 and 4.

This effectively reduces the problem from one of finding permutations of a list of four elements to a list of three elements. Once you continue reducing to 2 and then 1 element, you have all of them.

Answer 2

the simplest way I can think to explain this is by using some pseudo code

so

list of 1, 2 ,3
for each item in list
    templist.Add(item)
    for each item2 in list
        if item2 is Not item
            templist.add(item)
               for each item3 in list
                   if item2 is Not item
                      templist.add(item)

                   end if
               Next
            end if

    Next
    permanentListofPermutaitons,add(templist)
    tempList.Clear()
Next

Now obviously this is not the most flexible way to do this, and doing it recursively would be a lot more functional by my tired sunday night brain doesn't want to think about that at this moment. If no ones put up a recursive version by the morning I'll do one.