Как получить все перестановки размеров {n, n-1, n-2, ... 1} из списка размера n эффективно?

Question

Я пытаюсь найти все перестановки из списка того же размера или меньше, чем список.

Например:

>>>allPermutations([a,b]) 
[[a,b], [b,a], [a], [b]] 

Это итеративный код, который я в настоящее время в питона. Я не уверен, насколько он эффективен в настоящее время.

import itertools 

def getAllPossibleSubSchedules(seq): 
    fullSet = set() 
    curSet = set() 
    curSet.add(tuple(seq)) 
    for i in reversed(range(1, len(seq) + 1)): 
     permutations = set() 
     for curTuple in curSet: 
      permutationsList = list(itertools.permutations(curTuple, i)) 
      for permutation in permutationsList: 
       permutations.add(permutation) 
     curSet = set() 
     for permutation in permutations: 
      curSet.add(permutation) 
      fullSet.add(permutation) 
    return fullSet 

Я уверен, что алгоритм будет производить суммирование п! от 1 -> n перестановки, которые быстро растут. До сих пор я создал рекурсивный способ сделать это, что невероятно медленно, потому что он выполняет много повторных операций. Я пытался сделать это с помощью итерации, но я не могу понять, как ограничить повторные операции. Я использую python, но psuedo-код также мне очень помог. Любая помощь будет оценена по достоинству. Заранее спасибо!

Answer 1

Я уверен, что ваши звонки permutations.add() и curSet.add() и fullSet.add() вызовут вашу рутину очень быстро ползать. Если вы продолжаете изменять размер массива, выделенная память будет «исчерпаться» и должно быть обнаружено новое местоположение. Это означает, что весь массив копируется. И затем вы добавляете еще один элемент - полоскание и повторение.

Вам необходимо вычислить количество необходимых элементов и предварительно выделить пространство для этого. Таким образом, если у вас есть 5 элементов, вам нужно выделить (5! + 5 * 4! + 10 * 3! + 10 * 2! + 5) x 5 элементов для конечного результата - и меньше для промежуточных результатов. Затем вы заполняете этот массив без перетасовки блоков памяти; это сделает вещи значительно быстрее.

Answer 2

Возможно перебрать все перестановки для списков со всеми возможными размерами. Для уточнения:

def all_permutations(input_list): 
    for i in xrange(len(input_list)): 
     sublist = input_list[:i] 
     for variant in permutations(sublist): 
      yield variant 

Answer 3

должно работать:

from itertools import permutations 

def allPermutations(seq): 
    return (x for i in range(len(seq),0,-1) for x in permutations(seq, i)) 

Например:

>>> list(allPermutations('abc')) 
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('a',), ('b',), ('c',)]