파이썬 알고리즘 - 순열, 조합

순열

# 내장 함수로 구현
>>> from itertools import permutations

>>> for i in permutations([1,2,3,4], 2):
...     print(i, end=" ")
... 
(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

# 재귀함수로 구현
def permutations(array, r, prefix="nothing"):
    for i in range(len(array)):
        if array[i] == prefix: continue
        if r == 1:
            yield [array[i]]
        else:
            prefix = array[i]
            for next in permutations(array, r-1, prefix):
                yield [array[i]] + next

중복순열

# 재귀함수로 구현
def product(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in product(array, r-1):
                yield [array[i]] + next

조합

# 내장 함수로 구현
>>> from itertools import combinations
>>> for i in combinations([1,2,3,4], 2):
...     print(i, end=" ")
... 
(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

# 재귀함수로 구현
def combinations(array, r):
    for i in range(len(array)):
        if r == 1: # 종료 조건
            yield [array[i]]
        else:
            for next in combinations(array[i+1:], r-1):
                yield [array[i]] + next

중복 조합

# 내장 함수로 구현
>>> from itertools import combinations_with_replacement
>>> 
>>> for cwr in combinations_with_replacement([1,2,3,4], 2):
...     print(cwr, end=" ")
... 
(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

# 재귀함수로 구현
def combinations_with_replacement(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            ## array[i+1: ] -> array[i: ] 변경
            for next in combinations_with_replacement(array[i:], r-1):
                yield [array[i]] + next