파이썬(Python) - 순열(Permutation)과 조합(Combination) 구현하기

1. 순열(Permutation)

 

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.

 

[1, 2, 3] 이라는 숫자들을 가지고 순열을 구현해보자.

그림으로 나타내면 다음과 같다.

 

경우의 수는 총 6개이다.

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

 

그리고 숫자들을 각각 i, j, k 라고할 때,

i,   j,   k

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

잘 살펴보면 규칙이 있다.

• i 에 나왔던 수는 j 에 나오지 않는다.
• i 와 j 에 나왔던 수는 k 에 나오지 않는다.

 

1-1 반복문 사용

 

규칙을 이용해 반복문으로 구현해보자.

for i in range(1, 4):
	for j in range(1, 4):
    		if i == j : continue #i와 j가 같다면 무시
        	for k in range(1, 4): #i와 j가 같지않다면 k반복문 실행
        		if i == k or j == k: continue #i==k 혹은 j==k 라면 무시
            		print(i, j, k) #아니라면 출력

#출력값
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

 

위 반복문에 continue가 있는 코드를 "use" 라는 배열을 준비해 1, 2, 3에 대해 "사용됐다" 혹은 "사용되지 않았다"를 구분할 것이다.

예를들어, use[1] = 1 이면 사용중이고 use[2] = 0 이면 사용중이 아닌 것이다.

 

use = [0] * 4
for i in range(1, 4):
	use[i] = 1
	for j in range(1, 4):
    		if use[j] : continue #use[j]가 사용중이라면 무시
        	use[j] = 1 #아니라면 사용중으로 해줘
        	for k in range(1, 4): 
        		if use[k] : continue #use[k]가 사용중이라면 무시
            		use[k] = 1 #아니라면 사용중으로 해줘
            		print(i, j, k)
            		use[k] = 0
		use[j] = 0
	use[i] = 0    

#출력값
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

 

여기에서 i, j, k 가 별도로 리스트로 저장되기를 원한다면? arr 이라는 배열을 만들어 넣어주면 된다.

use = [0] * 4
arr = [0] * 3

for i in range(1, 4):
	use[i] = 1
    	arr[0] = i
	for j in range(1, 4):
    		if use[j] : continue 
        	use[j] = 1 
            	arr[1] = j
        	for k in range(1, 4): 
        		if use[k] : continue 
            		use[k] = 1 
            		arr[2] = k
                    	print(arr)
                    	arr[2] = 0
                    	use[k] = 0
		arr[1] = 0
        	use[j] = 0
    	arr[0] = 0
	use[i] = 0    

#출력값
[1 2 3]
[1 3 2]
[2 1 3]
[2 3 1]
[3 1 2]
[3 2 1]

 

 

1-2 재귀 사용

 

위에 반복문을 이용하면 데이터가 늘어난다면 반복문도 끝없이 늘어나는 문제가 있다....!

따라서 재귀를 사용해줘야 한다.

 

data = [1, 2, 3] #데이터
n = len(data) #데이터 개수
use = [0] * n #데이터를 사용중인가 아닌가? use[1] = 1 이면 사용중
arr = [0] * n #어떤 데이터를 선택했는가? arr[1] = 2 이라면 내가 두번째로 뽑은 숫자는 2 가 되는 것이다.

def permutation(level): #level은 위에 그림에서 파란색
	if level >= n:
    	print(arr)
        return
        
	for i in range(n):
    		if use[i] : continue
        	use[i] = 1 #i 인덱스에 있는 데이터 사용중
        	arr[level] = data[i]
        	permutation(level+1)
        	arr[level] = 0
        	use[i] = 0 #사용해제

permutation(0)

#출력값
[1 2 3]
[1 3 2]
[2 1 3]
[2 3 1]
[3 1 2]
[3 2 1]

 

 

 

2. 조합(Combination)

 

조합은 데이터 집합에서 서로 다른 n개의 원소 중 순서에 상관없이 k개를 선택하는 것이다.

만약 {1, 2, 3, 4} => 2개를 선택한다고 할 때 {1, 2} , {2, 1} 은 값은 같은 경우이다. {1, 2} == {2, 1} 

따라서 한 가지만 경우의 수로 사용한다.

 

[1, 2, 3, 4] 이라는 숫자들을 가지고 2개를 선택해 조합한다면 경우의 수는 다음과 같다.

 

[1, 2]

[1, 3]

[1, 4]

[2, 3]

[2, 4]

[3, 4]

 

총 6개이다.

 

리스트 안에 있는 숫자들을 각각 i 와 j 라고 하였을 때,

 

 i    j

[1, 2]

[1, 3]

[1, 4]

[2, 3]

[2, 4]

[3, 4]

 

여기에도 규칙이 있다.

• i 는 데이터 개수가 4개일 때 3까지 뽑는다. 즉, n-1
• j는 (i + 1) 부터 마지막 n개까지 뽑는다.

 

2-1 반복문 사용

 

규칙을 이용해 반복문으로 구현해보자.

#n개 데이터에서 2개 데이터 뽑기
data = [1, 2, 3, 4]

def func(n):
	for i in range(n-1):
    		for j in range(i+1, n):
        		print(data[i], data[j]) 

func(data[n])

#출력값
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

 

반복문으로 조합을 구현할 수 있지만, 문제가 있다.

데이터 수가 달라지는 경우는 상관없지만 k개가 달라지는 경우 for문을 추가/감소 해야하는 작업이 필요하다.

#n개 데이터에서 3개 데이터 뽑기
n = 5

def func(n):
	for i in range(n-2):
    		for j in rnage(i+1, n-1):
        		for k in range(j+1, n):
            			print(i, j, k)

 

이 문제를 해결하기 위해선 재귀를 사용해야 한다.

 

 

2-2 재귀 사용

#N개 데이터에서 k개 데이터 뽑기
#level: 몇번째 선택을 하는 것인가!
N = 4
k = 3
arr = [0] * k
A = [1, 2, 3, 4]

def combi(level, S):
    #종료조건
    if level == k:
        print(arr)
        return

    for i in range(S, N-k+level+1): 
        arr[level] = A[i]
        combi(level+1, i+1)

combi(0, 0)

#출력값
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]