조합과 순열

1. 조합

• 집합에서 일부 원소를 취해 부분집합을 만드는 방법
• 서로 다른 n개의 원소에서 중복을 허용하지 않고 k개를 뽑는 경우의 수
• 순서가 없음

- 조합의 수(Python)

def combination(n, r):
    if n == r or r == 0: return 1
    else: return combination(n-1, r-1) + combination(n-1, r)
combination(5, 3)

- 중복 조합(Python)

def combination(comArr, n, r, index, target, arr):
    if r==0:print(comArr)
    elif target==n: return
    else:
        comArr[index] = arr[target]
        combination(comArr, n, r-1, index+1, target, arr)
        combination(comArr, n, r, index,target +1, arr)
arr = [1,2,3,4]
n = len(arr)
r = 3
comArr = [0]*r
combination(comArr, n, r, 0, 0, arr)

2. 순열

• n개의 원소에서 k개의 원소를 골라 순서를 뒤섞는 연산
• 순서가 있음
• DFS, visited 배열을 이용함

- 순열 출력(Python)

def permutation(permArr, arr, visited, depth, n, r):
    if depth == r:
        print(permArr)
        return
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = True
        permArr[depth] = arr[i]
        permutation(permArr, arr, visited, depth+1, n, r)
        visited[i]= False
        
arr = [1,2,3]
n = len(arr)
r = 3
permArr = [0]*r
visited = [False]*n
 
permutation(permArr, arr, visited, 0, n, r)

- 중복 순열(Python)

def permutation(permArr, arr, depth, n, r):
    if depth == r:
        print(permArr)
        return
    for i in range(n):
        permArr[depth] = arr[i]
        permutation(permArr, arr, depth+1, n, r)
        
arr = [1,2,3]
n = len(arr)
r = 3
permArr = [0]*r
 
permutation(permArr, arr, 0, n, r)