Как сгенерировать все перестановки списка в Python
Как вы генерируете все перестановки списка в Python, независимо от типа элементов в этом списке?
Например:
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]
43 ответа
Начиная с Python 2.6 (и если вы используете Python 3), у вас есть стандартный инструмент библиотеки для этого:itertools.permutations,
import itertools
list(itertools.permutations([1, 2, 3]))
Если по какой-то причине вы используете старый 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)
И в Python 2.6 и далее:
import itertools
itertools.permutations([1,2,3])
(возвращается как генератор. Использование list(permutations(l)) вернуться в виде списка.)
Следующий код с Python 2.6 и выше ТОЛЬКО
Во-первых, импорт itertools:
import itertools
Перестановка (порядок имеет значение):
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)]
Комбинация (порядок не имеет значения):
print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]
Декартово произведение (с несколькими итерациями):
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)]
Декартово произведение (с одной итерацией и само собой):
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)]
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')
#!/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 основана на алгоритме, представленном в книге " Компьютерные алгоритмы" Горовица, Сахни и Раджасекерана.
Это решение реализует генератор, чтобы избежать хранения всех перестановок в памяти:
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
Штатная реализация (без выхода - все сделаю в памяти):
def getPermutations(array):
if len(array) == 1:
return [array]
permutations = []
for i in range(len(array)):
# get all perm's of subarray w/o current item
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
permutations.append([array[i], *p])
return permutations
Реализация доходности:
def getPermutations(array):
if len(array) == 1:
yield array
else:
for i in range(len(array)):
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
yield [array[i], *p]
Основная идея состоит в том, чтобы пройти по всем элементам в массиве для 1-й позиции, а затем во 2-й позиции перебрать все остальные элементы без выбранного элемента для 1-й позиции и т. Д. Вы можете сделать это с помощью рекурсии, где критерий остановки - это получение массива из 1 элемента - в этом случае вы возвращаете этот массив.
В функциональном стиле
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]]
Совершенно очевидным способом на мой взгляд может быть также:
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
Следующий код представляет собой перестановку на месте данного списка, реализованную в виде генератора. Поскольку он возвращает только ссылки на список, список не должен изменяться вне генератора. Решение нерекурсивное, поэтому использует мало памяти. Хорошо работают также с несколькими копиями элементов в списке ввода.
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
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]
]
Я использовал алгоритм, основанный на системе факторных чисел. Для списка длины 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 длинным выстрелом.
Обратите внимание, что этот алгоритм имеет 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]
Можно действительно перебрать первый элемент каждой перестановки, как в ответе Цвенна; Я предпочитаю написать это решение так:
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, Это также намного более эффективно использует память, так как использует функцию генератора (через yield), как в решении Риккардо Рейеса.
Это вдохновлено реализацией Haskell, использующей понимание списка:
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
Для производительности, решение Numpy, вдохновленное Кнутом, (стр. 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
Отказ от ответственности: бесформенный плагин от автора пакета.:)
Пакет trotter отличается от большинства реализаций тем, что он генерирует псевдосписки, которые на самом деле не содержат перестановок, а скорее описывают сопоставления между перестановками и соответствующими позициями в упорядочении, что позволяет работать с очень большими "списками" перестановок, как показано в этой демонстрации, которая выполняет довольно мгновенные операции и выполняет поиск в псевдосписке, "содержащем" все перестановки букв в алфавите, без использования большего объема памяти или обработки, чем на типичной веб-странице.
В любом случае, чтобы сгенерировать список перестановок, мы можем сделать следующее.
import trotter
my_permutations = trotter.Permutations(3, [1, 2, 3])
print(my_permutations)
for p in my_permutations:
print(p)
Выход:
Псевдосписок, содержащий 6 3-перестановок [1, 2, 3]. [1, 2, 3] [1, 3, 2] [3, 1, 2] [3, 2, 1] [2, 3, 1] [2, 1, 3]
Если вы не хотите использовать встроенные методы, такие как:
import itertools
list(itertools.permutations([1, 2, 3]))
вы можете реализовать функцию перестановки самостоятельно
from collections.abc import Iterable
def permute(iterable: Iterable[str]) -> set[str]:
perms = set()
if len(iterable) == 1:
return {*iterable}
for index, char in enumerate(iterable):
perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])
return perms
if __name__ == '__main__':
print(permute('abc'))
# {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
print(permute(['1', '2', '3']))
# {'123', '312', '132', '321', '213', '231'}
Красота рекурсии:
>>> 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']
ДРУГОЙ ПОДХОД (без библиотек)
def permutation(input):
if len(input) == 1:
return input if isinstance(input, list) else [input]
result = []
for i in range(len(input)):
first = input[i]
rest = input[:i] + input[i + 1:]
rest_permutation = permutation(rest)
for p in rest_permutation:
result.append(first + p)
return result
Ввод может быть строкой или списком
print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
Вот алгоритм, который работает со списком без создания новых промежуточных списков, аналогично решению Бер на /questions/22133164/kak-sgenerirovat-vse-perestanovki-spiska-v-python/22133227#22133227.
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
Этот алгоритм является наиболее эффективным, он избегает передачи массивов и манипуляций при рекурсивных вызовах, работает в 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)
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:]))
Прости мою неграмотность на питоне, потому что я не буду предлагать решение на питоне. Так как я не знаю, какой метод python 2.6 использует для генерации перестановок, а метод eliben похож на генерацию перестановок Джонсона-Троттера, вы можете найти статью в Википедии о перестановках и их генерации, которая очень похожа на функцию unrank в статье Мирволда и Руски.
Мне кажется, что это можно использовать в генераторе так же, как и в других ответах, чтобы значительно уменьшить требования к памяти. Просто помните, что перестановки не будут в лексикографическом порядке.
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)
Генерация всех возможных перестановок
Я использую 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)
Я вижу, что внутри этих рекурсивных функций происходит много итераций, а не просто рекурсия...
так что для тех из вас, кто не может соблюдать даже один цикл, вот грубое, совершенно ненужное полностью рекурсивное решение
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])
Чтобы сэкономить много часов на поиске и экспериментировании, вот решение для нерекурсивных перестановок в 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.
В любом случае мы могли бы использовать библиотеку sympy, а также поддержку перестановок мультимножества
import sympy
from sympy.utilities.iterables import multiset_permutations
t = [1,2,3]
p = list(multiset_permutations(t))
print(p)
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Ответ очень вдохновлен Get all permutations of a numpy array
def permutate(l):
for i, x in enumerate(l):
for y in l[i + 1:]:
yield x, y
if __name__ == '__main__':
print(list(permutate(list('abcd'))))
print(list(permutate([1, 2, 3, 4])))
#[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]
#[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]