Вопрос по python, permutation, combinatorics, algorithm, python-2.5 – Как сгенерировать все перестановки списка в Python

485

Как вы генерируете все перестановки списка в Python, независимо от типа элементов в этом списке?

Например:

<code>permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
</code>
@FlipMcF «Будет трудно решить эту проблему». в полиномиальное время, учитывая, что факториальному времени требуется даже просто перечислить выходные данные ... так что нет, это невозможно. Thomas
Я согласен с рекурсивным, принятым ответом - СЕГОДНЯ. Тем не менее, это все еще остается огромной проблемой информатики. Принятый ответ решает эту проблему с экспоненциальной сложностью (2 ^ N N = len (список)) Решите его (или докажите, что вы можете ") за полиномиальное время :) См." Задача коммивояжера " FlipMcF

Ваш Ответ

30   ответов
13

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res
36
def permutations(head, tail=''):
    if len(head) == 0: print tail
    else:
        for i in range(len(head)):
            permutations(head[0:i] + head[i+1:], tail+head[i])

называется как:

permutations('abc')
Зачем печатать хвост, а затем возвращать None? Почему бы не вернуть хвост вместо этого? Почему бы ничего не вернуть?
-3

новки, так и комбинации для решения вашей проблемы

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))
11

def addperm(x,l):
    return [ l[0:i] + [x] + l[i:]  for i in range(len(l)+1) ]

def perm(l):
    if len(l) == 0:
        return [[]]
    return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]

print perm([ i for i in range(3)])

Результат:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
3

поскольку я не буду предлагать решение на питоне. Поскольку я не знаю, какой метод python 2.6 использует для генерации перестановок, а eliben-ы похожи на генерацию перестановок Джонсона-Троттера, вы можете поискать статью в википедии наПерестановки и их генерация это выглядит как функция unrank вбумага Мирволда и Руски.

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

7

n factorial сложность времени, гдеn длина входного списка

Распечатать результаты на бегу:

global result
result = [] 

def permutation(li):
if li == [] or li == None:
    return

if len(li) == 1:
    result.append(li[0])
    print result
    result.pop()
    return

for i in range(0,len(li)):
    result.append(li[i])
    permutation(li[:i] + li[i+1:])
    result.pop()    

Пример:

permutation([1,2,3])

Выход:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
0
def permutation(word, first_char=None):
    if word == None or len(word) == 0: return []
    if len(word) == 1: return [word]

    result = []
    first_char = word[0]
    for sub_word in permutation(word[1:], first_char):
        result += insert(first_char, sub_word)
    return sorted(result)

def insert(ch, sub_word):
    arr = [ch + sub_word]
    for i in range(len(sub_word)):
        arr.append(sub_word[i:] + ch + sub_word[:i])
    return arr


assert permutation(None) == []
assert permutation('') == []
assert permutation('1')  == ['1']
assert permutation('12') == ['12', '21']

print permutation('abc')

1

lot итерации внутри этих рекурсивных функций, не совсемpure рекурсию ...

так что для тех из вас, кто не может придерживаться даже одного цикла, вот грубое, совершенно ненужное полностью рекурсивное решение

def all_insert(x, e, i=0):
    return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []

def for_each(X, e):
    return all_insert(X[0], e) + for_each(X[1:],e) if X else []

def permute(x):
    return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])


perms = permute([1,2,3])
-1

def permutations(arr):
  if not arr:
    return
  print arr
  for idx, val in enumerate(arr):
    permutations(arr[:idx]+arr[idx+1:])
322

И вPython 2.6 и далее:

import itertools
itertools.permutations([1,2,3])

(возвращается как генератор. Использованиеlist(permutations(l)) вернуться в виде списка.)

Работает и в Python 3
Обратите внимание, что существуетr параметр, напримерitertools.permutations([1,2,3], r=2), который будет генерировать все возможные перестановки, выбирая 2 элемента:[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
5

ния:

def permutation(list):
    if len(list) == 0:
        return [[]]
    else:
        return [[x] + ys for x in list for ys in permutation(delete(list, x))]

def delete(list, item):
    lc = list[:]
    lc.remove(item)
    return lc
14

реализованную в виде генератора. Поскольку он возвращает только ссылки на список, список не должен изменяться вне генератора. Решение нерекурсивное, поэтому использует мало памяти. Хорошо работают также с несколькими копиями элементов в списке ввода.

def permute_in_place(a):
    a.sort()
    yield list(a)

    if len(a) <= 1:
        return

    first = 0
    last = len(a)
    while 1:
        i = last - 1

        while 1:
            i = i - 1
            if a[i] < a[i+1]:
                j = last - 1
                while not (a[i] < a[j]):
                    j = j - 1
                a[i], a[j] = a[j], a[i] # swap the values
                r = a[i+1:last]
                r.reverse()
                a[i+1:last] = r
                yield list(a)
                break
            if i == first:
                a.reverse()
                return

if __name__ == '__main__':
    for n in range(5):
        for a in permute_in_place(range(1, n+1)):
            print a
        print

    for a in permute_in_place([0, 0, 1, 1, 1]):
        print a
    print
3
def pzip(c, seq):
    result = []
    for item in seq:
        for i in range(len(item)+1):
            result.append(item[i:]+c+item[:i])
    return result


def perm(line):
    seq = [c for c in line]
    if len(seq) <=1 :
        return seq
    else:
        return pzip(seq[0], perm(seq[1:]))
254

The following code with Python 2.6 and above ONLY

Во-первых, импортitertools:

import itertools
Permutation (order matters):
print list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]
Combination (order does NOT matter):
print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]
Cartesian product (with several iterables):
print list(itertools.product([1,2,3], [4,5,6]))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]
Cartesian product (with one iterable and itself):
print list(itertools.product([1,2], repeat=3))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
+1! Ссылка на документы:docs.python.org/2/library/itertools.html#itertools.permutations
3

который работает со списком без создания новых промежуточных списков, аналогичных решению Бер наhttps://stackoverflow.com/a/108651/184528.

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3, 4]):
    print p

Вы можете попробовать код для себя здесь:http://repl.it/J9v

0

Counter

from collections import Counter

def permutations(nums):
    ans = [[]]
    cache = Counter(nums)

    for idx, x in enumerate(nums):
        result = []
        for items in ans:
            cache1 = Counter(items)
            for id, n in enumerate(nums):
                if cache[n] != cache1[n] and items + [n] not in result:
                    result.append(items + [n])

        ans = result
    return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]

1

вот решение для нерекурсивных перестановок в Python, которое также работает с Numba (начиная с версии 0.41):

@numba.njit()
def permutations(A, k):
    r = [[i for i in range(0)]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if (a in b)==False]
    return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Чтобы произвести впечатление о производительности:

%timeit permutations(np.arange(5),5)

243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms

%timeit list(itertools.permutations(np.arange(5),5))
15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s

Так что используйте эту версию, только если вам нужно вызывать ее из функции njoted, в противном случае предпочтите реализацию itertools.

20
#!/usr/bin/env python

def perm(a, k=0):
   if k == len(a):
      print a
   else:
      for i in xrange(k, len(a)):
         a[k], a[i] = a[i] ,a[k]
         perm(a, k+1)
         a[k], a[i] = a[i], a[k]

perm([1,2,3])

Выход:

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

Поскольку я меняю содержимое списка, в качестве входных данных требуется изменяемый тип последовательности. Например.perm(list("ball")) будет работать иperm("ball") не будет, потому что вы не можете изменить строку.

Эта реализация Python основана на алгоритме, представленном в книге.Computer Algorithms by Horowitz, Sahni and Rajasekeran.

Я предполагаю, что k - длина или перестановки. Для k = 2 выхода [1, 2, 3]. Разве это не должно быть (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) ??
10
list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
            for a in list2Perm
            for b in list2Perm
            for c in list2Perm
            if ( a != b and b != c and a != c )
            ]
print listPerm

Выход:

[
    [1, 2.0, 'three'], 
    [1, 'three', 2.0], 
    [2.0, 1, 'three'], 
    [2.0, 'three', 1], 
    ['three', 1, 2.0], 
    ['three', 2.0, 1]
]
@James: Меня немного смущает O (n log n), которое вы даете: количество перестановок равно n !, что уже намного больше, чем O (n log n); Итак, я не могу видеть, как решение может быть O (n log n). Однако это правда, что это решение находится в O (n ^ n), что намного больше, чем n !, что ясно из приближения Стирлинга.
Хотя технически это дает желаемый результат, вы решаете что-то, что может быть O (n lg n) в O (n ^ n) - «слегка». неэффективно для больших наборов.
373

Starting with Python 2.6 (и если вы используете Python 3), у вас естьstandard-library Инструмент для этого:itertools.permutations.

Если вы используетеolder Python (<2.6) по какой-то причине или просто любопытно узнать, как это работает, вот один хороший подход, взятый изhttp://code.activestate.com/recipes/252178/:

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                # nb elements[0:1] works in both string and list contexts
                yield perm[:i] + elements[0:1] + perm[i:]

Несколько альтернативных подходов перечислены в документацииitertools.permutations, Вот один из них:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

И еще один, основанный наitertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)
Они также достигают предела рекурсии (и умирают) с большими списками
Это и другие рекурсивные решения потенциально могут израсходовать всю оперативную память, если перестановочный список достаточно большой
Не простоa генератор. Он использует вложенные генераторы, каждый из которых уступает предыдущему в стеке вызовов, в случае, если это неясно. Он использует O (n) памяти, что хорошо.
PS: я исправил это, сfor i in range(len(elements)) вместоfor i in range(len(elements)+1), На самом деле, выделенный элементelements[0:1] может быть вlen(elements) разные позиции, в результате неlen(elements)+1.
bgbg, dbr: используется генератор, поэтому сама функция не потребляет память. Вам осталось узнать, как использовать итератор, возвращаемый all_perms (скажем, вы можете записывать каждую итерацию на диск и не беспокоиться о памяти). Я знаю, что этот пост старый, но я пишу его для всех, кто читает его сейчас. Кроме того, теперь лучшим способом было бы использовать itertools.permutations (), как отмечали многие.
8

система факторных чисел- Для списка длины n вы можете собрать каждый элемент перестановки за элементом, выбирая из элементов, оставленных на каждом этапе. У вас есть n вариантов для первого элемента, n-1 для второго и только один для последнего, так что вы можете использовать цифры числа в системе факторных чисел в качестве индексов. Таким образом, числа от 0 до n! -1 соответствуют всем возможным перестановкам в лексикографическом порядке.

from math import factorial
def permutations(l):
    permutations=[]
    length=len(l)
    for x in xrange(factorial(length)):
        available=list(l)
        newPermutation=[]
        for radix in xrange(length, 0, -1):
            placeValue=factorial(radix-1)
            index=x/placeValue
            newPermutation.append(available.pop(index))
            x-=index*placeValue
        permutations.append(newPermutation)
    return permutations

permutations(range(3))

выход:

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Этот метод не рекурсивный, но он немного медленнее на моем компьютере, и xrange вызывает ошибку, когда n! слишком велик, чтобы преобразовать его в длинное целое число C (для меня n = 13). Этого было достаточно, когда я нуждался в этом, но это далеко не itertools.permutations длинным выстрелом.

Привет, добро пожаловать в Stack Overflow. Хотя публикация метода грубой силы имеет свои преимущества, если вы не думаете, что ваше решение лучше принятого решения, вам, вероятно, не следует публиковать его (особенно по старому вопросу, на который уже так много ответов).
Я на самом деле искал не-библиотечный подход грубой силы, так что спасибо!
2

он избегает передачи массивов и манипуляций при рекурсивных вызовах, работает в Python 2, 3:

def permute(items):
    length = len(items)
    def inner(ix=[]):
        do_yield = len(ix) == length - 1
        for i in range(0, length):
            if i in ix: #avoid duplicates
                continue
            if do_yield:
                yield tuple([items[y] for y in ix + [i]])
            else:
                for p in inner(ix + [i]):
                    yield p
    return inner()

Использование:

for p in permute((1,2,3)):
    print(p)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
2

Я использую python3.4:

def calcperm(arr, size):
    result = set([()])
    for dummy_idx in range(size):
        temp = set()
        for dummy_lst in result:
            for dummy_outcome in arr:
                if dummy_outcome not in dummy_lst:
                    new_seq = list(dummy_lst)
                    new_seq.append(dummy_outcome)
                    temp.add(tuple(new_seq))
        result = temp
    return result

Тестовые случаи:

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)
0

def permutes(input,offset):
    if( len(input) == offset ):
        return [''.join(input)]

    result=[]        
    for i in range( offset, len(input) ):
         input[offset], input[i] = input[i], input[offset]
         result = result + permutes(input,offset+1)
         input[offset], input[i] = input[i], input[offset]
    return result

# input is a "string"
# return value is a list of strings
def permutations(input):
    return permutes( list(input), 0 )

# Main Program
print( permutations("wxyz") )
3
from __future__ import print_function

def perm(n):
    p = []
    for i in range(0,n+1):
        p.append(i)
    while True:
        for i in range(1,n+1):
            print(p[i], end=' ')
        print("")
        i = n - 1
        found = 0
        while (not found and i>0):
            if p[i]<p[i+1]:
                found = 1
            else:
                i = i - 1
        k = n
        while p[i]>p[k]:
            k = k - 1
        aux = p[i]
        p[i] = p[k]
        p[k] = aux
        for j in range(1,(n-i)/2+1):
            aux = p[i+j]
            p[i+j] = p[n-j+1]
            p[n-j+1] = aux
        if not found:
            break

perm(5)
6

можно перебирать первый элемент каждой перестановки, как в ответе tzwenn; Я предпочитаю написать это решение так:

def all_perms(elements):
    if len(elements) <= 1:
        yield elements  # Only permutation possible = no permutation
    else:
        # Iteration over the first element in the result permutation:
        for (index, first_elmt) in enumerate(elements):
            other_elmts = elements[:index]+elements[index+1:]
            for permutation in all_perms(other_elmts): 
                yield [first_elmt] + permutation

Это решение примерно на 30% быстрее, очевидно, благодаря рекурсии, заканчивающейся вlen(elements) <= 1 вместо0. It is also much more memory-efficient, as it uses a generator function (through yield), как в решении Риккардо Рейеса.

3

>>> import copy
>>> def perm(prefix,rest):
...      for e in rest:
...              new_rest=copy.copy(rest)
...              new_prefix=copy.copy(prefix)
...              new_prefix.append(e)
...              new_rest.remove(e)
...              if len(new_rest) == 0:
...                      print new_prefix + new_rest
...                      continue
...              perm(new_prefix,new_rest)
... 
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']
21

чтобы избежать хранения всех перестановок в памяти:

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto
4

Кнут, (стр. 22):

from numpy import empty, uint8
from math import factorial

def perms(n):
    f = 1
    p = empty((2*n-1, factorial(n)), uint8)
    for i in range(n):
        p[i, :f] = i
        p[i+1:2*i+1, :f] = p[:i, :f]  # constitution de blocs
        for j in range(i):
            p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f]  # copie de blocs
        f = f*(i+1)
    return p[:n, :]

Копирование больших блоков памяти экономит время - это в 20 раз быстрее, чемlist(itertools.permutations(range(n)) :

In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop

In [2]: %timeit -n100 perms(10) 
100 loops, best of 3: 40 ms per loop
1

Другое решение:

def permutation(flag, k =1 ):
    N = len(flag)
    for i in xrange(0, N):
        if flag[i] != 0:
            continue
        flag[i] = k 
        if k == N:
            print flag
        permutation(flag, k+1)
        flag[i] = 0

permutation([0, 0, 0])

Похожие вопросы