리스트에서 가능한 순열을 모두 구하는 법

조회수 14475회

리스트의 원소로 가능한 순열을 모두 구하려면 어떻게 해야 할까요?

예를 들어

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 답변

  • 좋아요

    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)
    

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)