순열과 조합 (Permutation & Combination)

순열(Permutation)은 주어진 집합에서 원소를 선택하여 순서에 맞게 나열하는 방법이며, 조합(Combination)은 주어진 집합에서 원소를 선택하여 순서에 상관없이 나열하는 방법이다.

Baekjoon - Combinatorics

다음은 순열과 조합 문제에 사용될 수 있는 코드이다:

Permutation

• 순열 (Permutation)
  • 순열은 주어진 집합의 원소들을 모두 이용하여 가능한 모든 순서대로 배열하는 방법을 의미한다.
  • ex. 집합 {A, B, C}에서 2개의 원소를 선택하여 만들 수 있는 순열은 AB, AC, BA, BC, CA, CB 총 6가지이다.

• 중복 순열 (Repetition Permutation)
  • 중복 순열은 주어진 집합에서 원소를 중복을 허용하여 r번 선택하여 나열하는 방법을 의미한다.
  • ex. 집합 {A, B, C}에서 2개의 원소를 중복을 허용하여 선택하여 만들 수 있는 중복순열은 AA, AB, AC, BA, BB, BC, CA, CB, CC 총 9가지이다.

import itertools

# 순열
def permutations(arr, n):

    result = []

    if n == 0:
        return[[]]

    for (i, num) in enumerate(arr):
        for j in permutations(arr[:i] + arr[i + 1:], n-1):
            result.append([num] + j)

    return result

# [[0, 1], [0, 2], [0, 3], [1, 0], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [3, 2]]
result = permutations([0,1,2,3], 2)
result = list(itertools.permutations([0,1,2,3], 2))

import itertools

# 중복 순열
def permutations_with_replacement(arr, n):

    result = []

    if n == 0:
        return[[]]

    for (i, num) in enumerate(arr):
        for j in permutations(arr, n-1):
            result.append([num] + j)

    return result

# [[0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [1, 3], [2, 0], [2, 1], [2, 2], [2, 3], [3, 0], [3, 1], [3, 2], [3, 3]]
result = permutations_with_replacement([0,1,2,3], 2)
result = list(itertools.product([0,1,2,3], repeat=2))

Combination

• 조합 (Combination)
  • 조합은 주어진 집합에서 원소들을 순서에 상관없이 r개를 선택하는 방법을 의미한다.
  • 집합 {A, B, C}에서 2개의 원소를 선택하여 만들 수 있는 조합은 AB, AC, BC로 총 3가지이다.

• 중복 조합 (Repetition Combination)
  • 중복 조합은 주어진 집합에서 원소를 중복을 허용하여 r번 선택하는 방법을 의미한다.
  • 집합 {A, B, C}에서 2개의 원소를 중복을 허용하여 선택하여 만들 수 있는 중복 조합은 AA, AB, AC, BB, BC, CC 총 6가지이다.

import itertools

# 조합
def combinations(arr, n):

    result =[]

    if n == 0:
        return [[]]

    for (i, num) in enumerate(arr):
        for j in combinations(arr[i + 1:], n-1):
            result.append([num] + j)

    return result

# [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
result = combinations([0,1,2,3], 2)
result = list(itertools.combinations([0,1,2,3], 2))

import itertools

# 중복 조합
def combinations_with_replacement(arr, n):

    result =[]

    if n == 0:
        return [[]]

    for (i, num) in enumerate(arr):
        for j in combinations_with_replacement(arr[i:], n-1):
            result.append([num] + j)

    return result

# [[0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
result = combinations_with_replacement([0,1,2,3], 2)
result = list(itertools.combinations_with_replacement([0,1,2,3], 2))