목록의 요소 유형에 관계없이 파이썬에서 목록의 모든 순열을 어떻게 생성합니까?
예를 들면 다음과 같습니다.
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]답변
Python 2.6부터 (그리고 Python 3을 사용하는 경우)이를위한 표준 라이브러리 도구가 itertools.permutations있습니다.
import itertools
list(itertools.permutations([1, 2, 3]))당신이 사용하는 경우 이전의 파이썬 (<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)답변
그리고 파이썬 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 구현은 Horowitz, Sahni 및 Rajasekeran의 Computer Algorithms 책에 제시된 알고리즘에서 영감을 얻었습니다 .
답변
이 솔루션은 메모리에서 모든 순열을 유지하지 않도록 생성기를 구현합니다.
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 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]]