순열과 조합

오민준·2022년 9월 22일
0

0. 서두

  • 알고리즘 문제 풀이에 필요한 순열과 조합을 정리한다.

1. 순열

  • Permutation
  • 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 가짓수이다.
  • 다시 말하면 n개 중에 r개를 선택하여 만들 수 있는 모든 경우의 수를 의미한다.
def perm(arr, n):
    result = []
    if n > len(arr):
        return result

    if n == 1:
        for i in arr:
            result.append([i])

    elif n > 1:
        for i in range(len(arr)):
            ans = [i for i in arr]
            ans.remove(arr[i])
            for j in perm(ans, n-1):
                result.append([arr[i]]+j)

    return result

arr = [1, 2, 3]

print(Perm(arr, 1)) # [[1], [2], [3]]
print(Perm(arr, 2)) # [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
print(Perm(arr, 3)) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

2. 조합

  • Combination
  • 서로 다른 n개 중에서 r개를(n≥r) 취하여 조를 만들 때, 각각의 조를 조합이라고 한다
  • 다시 말하면 n개 중에 r개를 순서에 상관 없이 뽑은 경우의 수를 의미한다.
def comb(arr, n):
    result = []
    if n > len(arr):
        return result

    if n == 1:
        for i in arr:
            result.append([i])

    elif n > 1:
        for i in range(len(arr)-n+1):
            for j in comb(arr[i+1:], n-1):
                result.append([arr[i]]+j)

    return result

arr = [1, 2, 3]

print(comb(arr, 1)) # [[1], [2], [3]]
print(comb(arr, 2)) # [[1, 2], [1, 3], [2, 3]]
print(comb(arr, 3)) # [[1, 2, 3]]

3. itertools

  • 내장함수로 쉽게 순열과 조합을 사용할 수 있다.
  • 다만 itertools는 코딩 테스트에서 사용하지 못하는 경우가 있으므로 직접 구현하는 방법을 먼저 익히는 것이 중요하다.
from itertools import combinations
from itertools import permutations

arr = [1, 2, 3]

print(list(combinations(arr, 2)))  # [(1, 2), (1, 3), (2, 3)]
print(list(combinations(arr, 3)))  # [(1, 2, 3)]

print(list(permutations(arr, 2)))  # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(list(permutations(arr, 3)))  # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
profile
ChatGPT Driving Development

0개의 댓글