перестановки с фиксированным предыдущим элементом в Python

Question

Итак, я столкнулся с проблемой перестановок с фиксированным предыдущим элементом в списке.Итак, у меня есть список, который представляет собой упорядоченную последовательность чисел от 1 до n.

РЕДАКТИРОВАТЬ

вот переформулировка моего вопроса: вы можете представить граф дерева?Итак, 1-й уровень - это верхняя (также известная как родительская) вершина.Итак, если у нас есть вершина, подобная [1, 2, 3, 4], наш следующий шаг - сделать перестановки, вставив все числа в позицию n , это означает, что на выходе мы получим следующее:

1,1 лвл [1, 2, 3, 4]

2,1 лвл [1, 2, 4, 3]

3,1 лвл [1, 3, 4, 2]

4,1 лвл [2, 3, 4, 1]

Итак, затем мы смотрим на уровень 1.1 и делаем перестановки n-1-го элемента (4 фиксирован и не участвуем в перестановке на этом уровне).Вывод будет:

1.1.1 lvl [1, 2, 3, 4]

1.1.2 lvl [1, 3, 2, 4]

1.1.3 lvl [2, 3, 1, 4]

мы взяли 1.1.1 lvl и исправили элемент n-2 (как видите, нет смысла исправлять 1-й элемент).Таким образом, на этом уровне мы зафиксировали 3 и 4, что составляет n-1 и n й элементы, выход:

1.1.1.1 lvl [1, 2, 3, 4]

1.1.1.2 lvl [2, 1, 3, 4]

Мы обедали здесь, но еще не закончили.Перейти на уровень выше (это уровень 1.1.2).И переставить это.Здесь мы зафиксировали n-1 th элемент (это 2) и n th (это 4)

1.1.2.1 lvl [1, 3, 2, 4]

1.1.2.2 lvl [3, 1, 2, 4]

Закончено здесь.GOTO на верхнем уровне.Здесь зафиксированы 1 и 4.Итак,

1.1.3.1 lvl [2, 3, 1, 4]

1.1.3.2 lvl [3, 2, 1, 4]

Мы закончили уровень 1.1 и перейдем к 2.1, где мы повторяем то же самоепроцедура.

Итак, вопрос: как это сделать в python?

Answer 1

Перестановки в ваших результатах отличаются от предыдущего элемента заменой двух элементов.

Замена двух элементов соответствует ребру в пермутоэдре.

Это говорит о том, что вы пытаетесь посетитьвершины в пермутоэдре по некоторым критериям.Можете ли вы объяснить, что такое критерии в геометрических терминах?

Например, один из возможных вопросов - как генерировать все возможные перестановки, меняя местами только два элемента на каждом ходу.Это соответствует нахождению гамильтонова пути на пермутоэдре.Ответ на этот вопрос дает алгоритм Штейнхауса-Джонсона-Троттера , который дает метод O (n) для нахождения следующей перестановки из заданной позиции.

EDIT

Вот пример кода Python для обновленного вопроса:

def perms(A):
    if len(A)==1:
        yield A
    for i in xrange(len(A)-1,-1,-1):
        for B in perms(A[:i]+A[i+1:]):
            yield B+A[i:i+1]

Запуск

for a in perms([1,2,3,4]):
    print a

выводит следующее:

[1, 2, 3, 4]
[2, 1, 3, 4]
[1, 3, 2, 4]
[3, 1, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[1, 2, 4, 3]
[2, 1, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 3, 4, 2]
[3, 1, 4, 2]
[1, 4, 3, 2]
[4, 1, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[2, 3, 4, 1]
[3, 2, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]

Answer 2

Вы всегда можете использовать itertools.permutations.

from itertools import permutations
perm = permutations([1, 2, 3, 4])
while True:
    try:
        print perm.next() # perm.next() gives a tuple of the next permutation
    except StopIteration:
        break

Answer 3

Я надеюсь, что это то, что вы хотели: я предпочел использовать Indeces 0,1,2,3 вместо 1,2,3,4

def switch(a,b,c):
    aux = a[b]
    a[b] = a[c]
    a[c] = aux
class perm():
    def __init__(self,mylist,txt,myreference,flag = None):
        self.mylist = []
        self.mylist.extend(mylist)
        self.myreference = myreference
        self.txt = txt
        if flag == None:
            print self.mylist,txt
    def make_perm(self):
        count = 0
        if self.myreference > 1:
            New = perm(self.mylist,self.txt+str(count),self.myreference-1,0)
            New.make_perm()
        for i in xrange(self.myreference-1,-1,-1):
            switch(self.mylist,i,self.myreference)
            count += 1
            New = perm(self.mylist,self.txt+str(count),self.myreference-1)
            New.make_perm()

N = 4            
A = perm(range(N),"",N-1)
A.make_perm()

Я надеюсь, вы понимаете, что, как только мы на[1, 2, 4, 3] и мы фиксируем 3 в 4-й позиции, нельзя 1,4,2,3 двигаться на пермутоэдре без изменения позиции 3.

Answer 4

Если стандартное библиотечное решение по какой-то причине не подходит, я могу посоветовать сделать рекурсивную функцию, которая работает с перестановками.

Подсказка на решение:

def perm(lst):
   if len(lst) == 1:  # single element list                                                                                                                                                           
       return [lst]

   res = []
   for last_item in lst:
       lst1 = filter(lambda x: x!= last_item, lst)  # ... without last_item                                                                                                                           
       for p in perm(lst1):                                                                                                                                                                
           res.append(p + [last_item])

   return res

Я хотел, чтобы решение было простым. Есть способы оптимизировать его, использовать генераторы и ленивые вычисления и т. Д.