순열과 조합 구현 (파이썬)

구현

재귀를 이용한 조합

• 첫번째 구현은 문자열을 조합하며 결과에 추가하고, 두번째는 함수를 반복적으로 호출할수록 for문의 범위를 좁혀간다.

def comb(arr, n):
    result = []
    if n == 0:
        return [[]]
    for i in range(len(arr)):
        for rest in comb(arr[i+1:], n-1):
            result.append([arr[i]] + rest)
    return result

print(comb(a, 2))
# a = [1,2,3,4]
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

result =[]
def comb2(arr, n, temp, start):
    if n==0:
        result.append(temp)
        return
    
    for i in range(start, len(arr)):
        comb2(arr,n-1, temp+[arr[i]], i+1)
    
    return result
print(comb2(a, 2, [], 0))      
# a = [1,2,3,4]
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

재귀를 이용한 순열

• 순열은 순서가 있기 때문에 조합과 달리 for문의 범위를 좁히지 못한다
• 대신 Check를 이용해 현재 값이 뽑혔는지 아닌지 판단을 한다.

check = [False] * len(a)
result = []
def perm(arr, n, temp):
    if n == 0:
        result.append(temp)
        return
    
    for i in range(len(arr)):
        if not check[i]:
            check[i] = True
            perm(arr, n-1, temp+[arr[i]])
            check[i] = False
    return result

print(perm(a, 2, []))
# a = [1,2,3,4]
# [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]