Home 순열과 조합 Python으로 알아보기
Post
Cancel

순열과 조합 Python으로 알아보기

순열과 조합, 중복순열과 중복조합에 대해 알아보고, Python으로 코드를 작성하겠습니다.

순열 (Permutation)

nPr = n! / (n-r)!

구현 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys

sys.stdin = open('src/input.txt')
input = sys.stdin.readline


# nPr
def permutation(n, r, k):
    if r == k:
        print(*res)
        return
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            res[k] = arr[i]
            permutation(n, r, k + 1)
            visited[i] = False
    return


# 3P2
arr = [1, 2, 3]
n = len(arr)
r = 2
res = [0] * r
visited = [False] * n

permutation(n, r, 0)  # 배열의 크기, 뽑는 개수, 깊이
1
[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]

구현 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def nPr(n, k):
    if k == n:
        print(*arr)
        return
    for i in range(k, n):
        arr[k], arr[i] = arr[i], arr[k]
        nPr(n, k + 1)
        arr[k], arr[i] = arr[i], arr[k]
    return


arr = [1, 2, 3]
n = len(arr)
r = 2

nPr(n, 0)
1
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]

조합 (Combination)

nCr = nPr / r!

구현 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# nCr
def combination(n, r, k, s):
    if r == k:
        print(*res)
        return
    for i in range(s, n - r + k + 1):
        res[k] = arr[i]
        combination(n, r, k + 1, i + 1)
    return


# 3C2
arr = [1, 2, 3]
n = len(arr)
r = 2
res = [0] * r

combination(n, r, 0, 0)  # 배열의 크기, 뽑는 개수, 깊이, 시작 인덱스
1
[1, 2], [1, 3], [2, 3]

구현 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# nCr
def combination(n, r, s):
    if r == 0:
        print(*res)
        return
    for i in range(s, n - r + 1):
        res[r - 1] = arr[i]  # res[2 - r] = arr[i]
        combination(n, r - 1, i + 1)
    return


# 3C2
arr = [1, 2, 3]
n = len(arr)
r = 2
res = [0] * r

combination(n, r, 0)  # 배열의 크기, 뽑는 개수, 깊이
1
[2, 1], [3, 1], [3, 2]

구현 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def nCr(n, r):
    if r == 0:
        print(*res)
    elif n < r:
        return
    else:
        res[r - 1] = arr[n - 1]
        nCr(n - 1, r - 1)
        nCr(n - 1, r)


arr = [1, 2, 3, 4]
n = len(arr)
r = 3
res = [0] * r
nCr(n, r)
1
[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]

구현 4

1
2
3
4
5
6
7
8
9
10
11
12
def nCr(i, j, k):
    print(i, j, k)
    return


n = 4
r = 2

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            nCr(i, j, k)
1
[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]

nCr의 개수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def num_of_combination(n, r):
    if r == 0:
        return 1
    elif n < r:
        return 0
    else:
        return num_of_combination(n - 1, r - 1) + num_of_combination(n - 1, r)


arr = [1, 2, 3, 4]
n = len(arr)
r = 3
res = [0] * r
print(num_of_combination(n, r))
1
4

중복순열

nπr = n^r

중복조합

nHr = n+r-1Cr

This post is licensed under CC BY 4.0 by the author.