[python] 파이썬 - 순열과 조합(itertools 활용 또는 dfs 활용 코드) 예제

itertools을 활용하면 순열과 조합을 쉽게 작성할 수 있다. 튜플의 형태로 결과를 리턴한다.

>> import itertools

>> a= [1,2,3]


>> # permutations
>> list(itertools.permutations(a)) 
[(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)]

>> list(itertools.permutations(a,2))
[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]


>> # combinations
>> list(itertools.combinations(a,2))  ## 'combinations()' requires r-value.
[(1,2),(1,3),(2,3)]


#첫번째 인자로 리스트가 아닌 튜플을 넣어도 된다.
lst = []
for i in range(1, 5):
    a = itertools.combinations((1,2,3), i)
    lst.extend(a)
print(lst)


lst = []
for i in range(1, 5):
    a = itertools.combinations(range(3), i)
    lst.extend(a)
print(lst)
>> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

 

라이브러리를 사용하지 않고 dfs를 활용하여 순열과 조합을 만들어낼 수 있다.

class Solution:
    def permute(self, nums:list, r = -1):
        if r < 0:
            r = len(nums)

        result = []

        def dfs(lst):
            if len(lst) == r:
                result.append(lst)
                return

            for num in nums:
                if not num in lst:
                    dfs(lst + [num])
        dfs([])
        return result

    def combine(self, nums: list, r = -1):
        if r < 0:
            r = len(nums)

        result = []

        def dfs(lst, unused):
            if len(lst) == r:
                result.append(lst)
                return

            for num in unused:
                idx = unused.index(num)
                dfs(lst + [num], unused[idx + 1:])

        dfs([], nums)
        return result


a = Solution().permute([1,2,3])      # nPn
b = Solution().permute([1,2,3,4],2)  # nPr
c = Solution().combine([1,2,3])      # nCn
d = Solution().combine([1,2,3,4],2)  # nCr
print(len(a), a)
print(len(b), b)
print(len(c), c)
print(len(d), d)

## result ##############################################################################
6 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
12 [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
1 [[1, 2, 3]]
6 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

 

++)

중복순열, 중복조합 추가

import itertools
a = [1, 2, 3]

r = itertools.permutations(a, 2)
for elem in r:
    print(elem)
print()
r = itertools.product(a, repeat=2)
for elem in r:
    print(elem)
print()
r = itertools.combinations(a, 2)
for elem in r:
    print(elem)
print()
r = itertools.combinations_with_replacement(a, 2)
for elem in r:
    print(elem)