[알고리즘] 기본 개념 정리 (9) - 경우의 수 계산을 위한 기초 조합론

집합의 분할과 스털링 수

• 그룹의 순서와 그룹 내 원소의 순서는 중요하지 않은 상황
• 서로 다른 열 개의 팀을 네 그룹으로 빈 그룹 없이 나누는 방법은?

• 제2종 스털링 수를 구하는 프로그램

S = list()
n = 10
k = 4

for i in range(0, 100):
    new_list = list()
    for j in range(0, 100):
        new_list.append(-1)
    S.append(new_list)

for i in range(1, n+1):
    for j in range(1, i+1):
        if (j == 1 or j == i):
            S[i][j] = 1
        else:
            S[i][j] = S[i-1][j-1] + (j*S[i-1][j])

print(S[n][k])

카탈란 수의 뜻과 그 응용

• Catalan number

n = int(input())

C = [1]

for round in range(1, n+1):
    new_C = 0
    i = 0
    j = round - 1
    while (j >= 0):
        new_C += C[i] * C[j]
        i += 1
        j -= 1
    C.append(new_C)

print(C[-1])

→ 정다각형의 분활 문제에 사용됨

→ 대각선 움직임의 문제에도 사용됨

 

def catalan_dp(n):
    # A dynamic programming based function to find nth
    # Catalan number

    # Table to store results of subproblems
    catalan = [0 for _ in range(n + 1)]

    # Initialize the first two values in the table
    catalan[0] = 1
    catalan[1] = 1

    # Fill entries in catalan[] using recursive formula
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i - j - 1]

    # Return the nth Catalan number
    return catalan[n]

# Function to calculate the number of different valid parenthesis sequences
def valid_parentheses_sequences(n):
    # The number of valid parenthesis sequences of length 2n is the nth Catalan number
    return catalan_dp(n)

# Example usage:
# Let's say we want to find the number of valid parentheses sequences for 3 pairs of parentheses
n_pairs = 3
number_of_sequences = valid_parentheses_sequences(n_pairs)
number_of_sequences

 

교란순열과 경우의 수

def derangement(n):
    # 기저 사례: D_1 = 0, D_2 = 1
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    # 첫 두 교란순열의 값을 저장
    a, b = 0, 1
    
    # 3부터 n까지의 교란순열을 계산
    for i in range(3, n+1):
        # 현재 교란순열을 계산
        cur = (i - 1) * (a + b)
        # 다음 계산을 위해 값을 갱신
        a, b = b, cur
    
    # n번째 교란순열 값 반환
    return b

# 주어진 문제의 N 값은 3입니다.
n = 3
# 교란순열의 수를 계산합니다.
derangement_n = derangement(n)
derangement_n