리스트에서 가능한 순열을 모두 구하는 법
조회수 14497회
리스트의 원소로 가능한 순열을 모두 구하려면 어떻게 해야 할까요?
예를 들어
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]
이런 식으로 구해주려면 어떻게 해야 되나요?
1 답변
-
파이썬 2.6이상:
파이썬 2.6 이상에서는 itertools.permutations()이 해당 기능을 지원합니다.
itertools.permutations(iterable[, r])은 iterable로 만들 수 있는 길이
r
의 순열을 return해줍니다.
r
을 지정하지 않은 경우r
은 iterable의 길이로 설정됩니다.import itertools mylist = [1,2,3] mypermuatation = itertools.permutations(mylist) for i in mypermuatation: print i
결과 :
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
파이썬 2.6 미만:
2.6 미만에서는 직접 만드는 수밖에 없습니다. 제가 추천하는 방법은
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:]
또는
#2.7.11 documentation - https://docs.python.org/2.7/library/itertools.html?highlight=permutations#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
또는
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)
댓글 입력