[Python] 순열(Permutation)과 조합(Combination)

순열

순열이란 서로 다른 n개중 r개를 선택하여 순서를 정해 나열할 수 있는 가짓수이다. 예를 들어 [A, B, C] 리스트가 있을 때  2개를 선택한 후 순서를 고려해서 나열할 수 있는 가짓수는 [(A,B), (A,C), (B, A), (B, C), (C, A), (C, B)] 총 6개이다.

 

 

순열 구현해보기

def permutation(arr, n):
    result = []
    if n == 0:
        return [[]]
    elif n == 1:
        return [[i] for i in arr]
    elif n >= 2:
        for i in range(len(arr)):
            elem = arr[i]
            p = permutation(arr[:i] + arr[i+1:], n-1)
            for rest in p:
                result.append([elem]+rest)
    return result

# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
print(permutation([1,2,3], 2))
# [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
print(permutation([1,2,3,4], 2))

 

순열 내장함수

from itertools import permutations
# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
print(list(permutation([1,2,3], 2)))
# [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
print(list(permutation([1,2,3,4], 2)))

 

조합

조합이란 서로 다른 n개 중에서 r개를 선택하여 순서를 고려하지 않고 나열할 수 있는 가짓수이다. 예를 들어 [A, B,C] 리스트가 있을 때 2개를 골라 순서를 고려하지 않고 나열하면 가짓수는 [(A, B), (A, C), (B, C)] 총 3가지이다.

 

조합 구현해보기

def combination(arr, n):
    result = []
    if n == 0:
        return [[]]
    
    if n == 1:
        return [[i] for i in arr]
    
    if n >= 2:
        for i in range(len(arr)):
            el = arr[i]
            c = combination(arr[i+1:], n-1)
            for rest in c:
                result.append([el]+rest)
    return result
    
# [['A', 'B'], ['A', 'C'], ['B', 'C']]  
print(combination(['A', 'B', 'C'], 2))

 

조합 내장함수

from itertools import combinations
# [['A', 'B'], ['A', 'C'], ['B', 'C']]
print(list(combination(['A', 'B', 'C'], 2)))