Перестановочные списки номеров Python с неожиданными результатами

Question

Я пытаюсь взять список чисел 0-9 включительно и вернуть все перестановки в списке. Я придумал две разные функции, которые в определенной степени возвращают ожидаемый результат, но я и не цель. Вот один, который возвращает правильные результаты для одного цикла:

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 

Возвраты:

[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] 

Хотя, когда я использую другой список в перестановке, она дает неожиданные результаты:

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] 

Когда он проходит через девять циклов правильно, он возвращается к 0-9. Поэтому я видел, что это связано с вызовом x.sort(). Поэтому я изменил эту функцию следующим образом:

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 

Теперь это не работает отлично до сдвига семи, и он идет к каждому второму. Я полагаю, что счет смешался, но я прохожу и не вижу его?

Answer 1

Попробуйте изменить x = static в последнем if заявлении x = static[:]. Проблема в том, что вы просто перепечатываете имя x в тот же список, к которому привязан static. Вы действительно хотите сделать копию того, к чему привязано static.

Answer 2

Лучшим решением было бы

from itertools import permutations 

, но если вы должны написать его самостоятельно, обычное решение является рекурсивным:

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: хорошо, проблема Эйлера требует иного подхода в целом ... трюк заключается не в том, чтобы генерировать все перестановки до 1 000 000 (что было бы слишком медленным), а для вычисления того, что должно быть миллионной перестановкой. Нет! способы упорядочения n элементов - вы можете рекурсивно использовать это на хвосте последовательности, чтобы выяснить, сколько подпоследовательностей нужно переставить, чтобы добраться до миллионной договоренности, и из этого выработать то, что должно быть.

Вам нужно написать что-то больше похоже на

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