Python number list permutations with unexpected results

Question

I am attempting to take a list of numbers 0-9 inclusive and return all the permutations of the list. I have come up with two different functions that return the expected result to a certain extent but, neither is exactly what I am aiming for. Here is one that returns the correct results for one cycle:

x = [0,1,2,3,4,5,6,7,8,9]

def test(x):
  place_holder = 9
  count = 9
  print x
  while count > 1:
    old_x = x[count]
    x[count] = x[count-1]
    x[count-1] = old_x
    count -= 1
    print x
    if count == 1:
      x.sort()
      place_holder -= 1
      count = place_holder

Returns:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 9, 6, 7, 8]
[0, 1, 2, 3, 4, 9, 5, 6, 7, 8]
[0, 1, 2, 3, 9, 4, 5, 6, 7, 8]
[0, 1, 2, 9, 3, 4, 5, 6, 7, 8]
[0, 1, 9, 2, 3, 4, 5, 6, 7, 8]
[0, 9, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 8, 6, 7, 9]
[0, 1, 2, 3, 4, 8, 5, 6, 7, 9]
[0, 1, 2, 3, 8, 4, 5, 6, 7, 9]
[0, 1, 2, 8, 3, 4, 5, 6, 7, 9]
[0, 1, 8, 2, 3, 4, 5, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 7, 5, 6, 8, 9]
[0, 1, 2, 3, 7, 4, 5, 6, 8, 9]
[0, 1, 2, 7, 3, 4, 5, 6, 8, 9]
[0, 1, 7, 2, 3, 4, 5, 6, 8, 9]
[0, 7, 1, 2, 3, 4, 5, 6, 8, 9]
[0, 1, 2, 3, 4, 6, 5, 7, 8, 9]
[0, 1, 2, 3, 6, 4, 5, 7, 8, 9]
[0, 1, 2, 6, 3, 4, 5, 7, 8, 9]
[0, 1, 6, 2, 3, 4, 5, 7, 8, 9]
[0, 6, 1, 2, 3, 4, 5, 7, 8, 9]
[0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
[0, 1, 2, 5, 3, 4, 6, 7, 8, 9]
[0, 1, 5, 2, 3, 4, 6, 7, 8, 9]
[0, 5, 1, 2, 3, 4, 6, 7, 8, 9]
[0, 1, 2, 4, 3, 5, 6, 7, 8, 9]
[0, 1, 4, 2, 3, 5, 6, 7, 8, 9]
[0, 4, 1, 2, 3, 5, 6, 7, 8, 9]
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
[0, 3, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 2, 1, 3, 4, 5, 6, 7, 8, 9]

Though when I use another list in the permutation, it gives unexpected results:

x = [1,0,2,3,4,5,6,7,8,9]

[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 0, 2, 3, 4, 5, 6, 9, 7, 8]
[1, 0, 2, 3, 4, 5, 9, 6, 7, 8]
[1, 0, 2, 3, 4, 9, 5, 6, 7, 8]
[1, 0, 2, 3, 9, 4, 5, 6, 7, 8]
[1, 0, 2, 9, 3, 4, 5, 6, 7, 8]
[1, 0, 9, 2, 3, 4, 5, 6, 7, 8]
[1, 9, 0, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 8, 6, 7, 9]
[0, 1, 2, 3, 4, 8, 5, 6, 7, 9]
[0, 1, 2, 3, 8, 4, 5, 6, 7, 9]
[0, 1, 2, 8, 3, 4, 5, 6, 7, 9]
[0, 1, 8, 2, 3, 4, 5, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 7, 5, 6, 8, 9]
[0, 1, 2, 3, 7, 4, 5, 6, 8, 9]
[0, 1, 2, 7, 3, 4, 5, 6, 8, 9]
[0, 1, 7, 2, 3, 4, 5, 6, 8, 9]
[0, 7, 1, 2, 3, 4, 5, 6, 8, 9]
[0, 1, 2, 3, 4, 6, 5, 7, 8, 9]
[0, 1, 2, 3, 6, 4, 5, 7, 8, 9]
[0, 1, 2, 6, 3, 4, 5, 7, 8, 9]
[0, 1, 6, 2, 3, 4, 5, 7, 8, 9]
[0, 6, 1, 2, 3, 4, 5, 7, 8, 9]
[0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
[0, 1, 2, 5, 3, 4, 6, 7, 8, 9]
[0, 1, 5, 2, 3, 4, 6, 7, 8, 9]
[0, 5, 1, 2, 3, 4, 6, 7, 8, 9]
[0, 1, 2, 4, 3, 5, 6, 7, 8, 9]
[0, 1, 4, 2, 3, 5, 6, 7, 8, 9]
[0, 4, 1, 2, 3, 5, 6, 7, 8, 9]
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
[0, 3, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 2, 1, 3, 4, 5, 6, 7, 8, 9]

Where it goes through the nine cycle properly then goes back to 0-9. So I could see this is because of the x.sort() call. So I changed this function to this:

def exp_test(x):
  static = []
  for i in x:
    static.append(i)
  place_holder = 9
  count = 9
  print x
  while count > 1:
    old_x = x[count]
    x[count] = x[count-1]
    x[count-1] = old_x
    count -= 1
    print x
    if count == 1:
      x = static
      place_holder -= 1
      count = place_holder

Now this works fine until the shift of the seven and it goes to every second number. I figure the count got mixed up but, I go through and don't see it?

Answer 1

The best solution would be

from itertools import permutations

but if you must write it yourself, the usual solution is recursive:

def permutations(seq):
    _len = len(seq)
    if _len:
        if _len==1:
            yield seq
        else:
            for p in permutations(seq[1:]):
                for i in range(_len):
                    yield p[:i] + seq[0:1] + p[i:]

Edit: well, the Euler problem requires a different approach altogether... the trick is not to generate all permutations up to 1,000,000 (which would be far too slow), but to calculate what the millionth permutation must be. There are n! ways to arrange n items - you can recursively use this on the tail of the sequence to figure out how many subsequences have to be rearranged to get to the millionth arrangement, and from that work out what the arrangement must be.

You need to write something more like

def nth_arrangement(seq, n):
    # you have to figure this bit out!

Answer 2

Try modifying x = static in the last if statement to x = static[:]. The problem is that you are simply rebinding the name x to the same list that static is bound to. You really want to make a copy of what static is bound to instead.