[Python] 조합, 순열, 중복순열

1️⃣ itertools 사용

• 간단하지만 시간 복잡도가 높기 때문에 자료 수가 매우 많으면 사용 X
  • 직접 구현해야 함 !!

조합

• 중복 X, 순서 X

from itertools import combinations

list = ['A', 'B', 'C']
result = list(combinations(list, 2))
result = [('A','B'), ('A','C'), ('B','C')]

• iterable 객체에서 r개 데이터 뽑는 경우의 수 나열
• combinations(모집합, 뽑을 개수)으로 사용

순열

• 중복 X, 순서 O

from itertools import permutations

list = ['A', 'B', 'C']
result = list(permutations(list,2))
result = [('A','B'), ('A','C'), ('B','A'), ('B','C'), ('C','A'), ('C','B')]

• permutations(모집합,뽑을 개수)으로 사용

중복 조합

• 중복 O, 순서 X

from itertools import combinations_with_replacement 

list = ['A', 'B', 'C']
result = list(combinations_with_replacement(list, 2))
result = [('A','A'), ('A','B'), ('A','C'), ('B','B'), ('B','C'), ('C','C')]

중복 순열

• 중복 O, 순서 O

from itertools import product 

list = ['A', 'B', 'C']
result = list(product(list, repeat=2))
result = [('A','A'), ('A','B'), ('A','C'), ('B','A'), ('B','B'), ('B','C'), ('C','A'), ('C''B'), ('C','C')]

• product(모집합, repeat=뽑을 개수)으로 사용

2️⃣ 직접 구현 by Python

• n개 중 r개 뽑는 경우
• 재귀 함수 이용

조합

• combination([0,1,2,3], 2)
  = ([0], combination([1, 2, 3], 1)) + ([1], combination([2, 3], 1)) + ([2], combination([3], 1)))

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

print(combination([0,1,2,3], 2))
# [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

순열

• permutation([0,1,2,3], 2)
  = ([0], permutation([1, 2, 3], 1)) + ([1], permutation([0, 2, 3], 1)) + ([2], permutation([0, 1, 3], 1)) + ([3], permutation([0, 1, 2], 1))

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