재귀함수를 이용한 순열 구현하기

1. 다중 for문을 이용해 단순히 순열을 생성하기

 

[1,2,3,4]의 모든 순열을 출력하라하면 어떻게 해야할까?

 

1부터 4까지 i,j,k,w를 잡고, i가 1부터 4중 하나를 선택하고,

 

j는 i에서 고르지 않은 1부터 4중에 하나 고르고

 

k는 i,j에서 고르지 않은 1부터 4중 하나를 고르고

 

w는 i,j,k에서 고르지 않은 나머지 하나를 고르고

 

for i in range(1,5):
    
    for j in range(1,5):
        
        if i != j:
            
            for k in range(1,5):
                
                if k != i and k != j:
                    
                    for w in range(1,5):
                        
                        if w != i and w != j and w != k:
                            
                            print(i,j,k,w)

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

2. 재귀함수를 이용한 순열1

 

하지만 위와 같이하면, 개수가 조금만 커지면, 하나하나 다 쓰기가 힘들다

 

6! 구할려면 변수 6개에 6중 for문을 써야하는데 가능하겠는가

 

------------------

 

원래 배열 p = [1,2,3,4]를 정의하고 여기서 순열을 모두 구해본다.

 

i = 0이면.. for j in range(0,4)를 순회하는데

 

0번과 0번을 서로 뒤바꾼다.. [1,2,3,4]

 

i+1 = 1번으로 이동해서  for j in range(1,4)를 순회하고.. 1번과 1번을 서로 뒤바꾼다 [1,2,3,4]

 

i+1 = 2번으로 이동해서  for j in range(2,4)를 순회하고.. 2번과 2번을 서로 뒤바꾼다 [1,2,3,4]

 

i+1 = 3번으로 이동해서  for j in range(3,4)를 순회하고.. 3번과 3번을 서로 뒤바꾼다 [1,2,3,4]

 

i+1 = 4번으로 이동하면  r=4와 동일하므로, p = [1,2,3,4] 하나의 순열 완성

 

다시 뒤로 이동해서..

 

""i+1 = 3번으로 이동해서  for j in range(3,4)를 순회하고.. 3번과 3번을 서로 뒤바꾼다 [1,2,3,4]""

 

여기는 j =3까지니까 패스

 

"" i+1 = 2번으로 이동해서  for j in range(2,4)를 순회하고.. 2번과 2번을 서로 뒤바꾼다 [1,2,3,4]""

 

여기서 j = 2가 끝났으니까, j=3에 대해 수행

 

현재 i = 2이고, j=3과 뒤바꾼다 [1,2,4,3]

 

다시 i+1=3으로 재귀적 이동

 

i+1 = 3번으로 이동해서  for j in range(3,4)를 순회하고.. [1,2,4,3]인 상태에서.. 3번과 3번을 서로 뒤바꾼다 [1,2,4,3]

 

그 후 i+1 = 4으로 재귀이동 하면, r=4와 동일해지므로 또 하나의 순열 p = [1,2,4,3] 완성

 

다시 뒤로 계속 이동

 

"" i+1 = 2번으로 이동해서  for j in range(2,4)를 순회하고.. 2번과 2번을 서로 뒤바꾼다 [1,2,3,4]""

 

여기서 j=3까지 전부 끝났으니까 현재 p = [1,2,4,3]에서 i=2, j=3이고 p[i],p[j] = p[j],p[i]를 수행 >> [1,2,3,4]

 

""i+1 = 1번으로 이동해서  for j in range(1,4)를 순회하고.. 1번과 1번을 서로 뒤바꾼다 [1,2,3,4]""

 

여기서 j=1이 끝났으니까, j=2가 수행.. 1번과 2번을 서로 뒤바꾼다. [1,3,2,4]

 

....

 

계속 반복하면 왜 저렇게 출력되었는지 알 수 있겠네

 

def permutation(i,r):
    
    if i == r: ##i번 인덱스가 원소의 개수와 동일해진다면...
        
        print(p) #완성된 하나의 순열 p로 수행할 행동 처리
    
    else:
        
        for j in range(i,r):
            
            p[i],p[j] = p[j],p[i] #i번과 j번을 서로 뒤바꾼다
            permutation(i+1,r) #i+1번을 결정하러 재귀적 이동
            p[i],p[j] = p[j],p[i] #모든 재귀 이동을 수행하면, 원래 자리로 복구
            

p = [1,2,3,4]

permutation(0,4)

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]

 

 

3. 재귀함수를 이용한 순열 구현2

 

단순히 자리를 바꾸는 위의 방법 말고도 j번 인덱스가 사용되었는지 아닌지를 체크하면서 구현할 수도 있다

 

조금 더 직관적일지도 몰라

 

used 배열을 순열을 만들고 싶은 배열의 j번째 원소가 사용되었으면 used[j] = 1, 사용되지 않았으면 0이라고 표시하여..

 

def permutation(i,r):
    
    if i == r:
        
        print(p) ##완성된 순열 p를 이용한 행동
        
    
    else:
        
        for j in range(r):
            
            if used[j] == 0: #a[j]가 사용되지 않았으면
                
                used[j] = 1 #a[j]를 사용하였고
                
                p[i] = a[j] #p의 i번째를 a[j]로 채우고
                
                permutation(i+1,r) #p의 i+1번째를 결정하러 이동
                
                used[j] = 0 #순열 완성 후에 a[j]를 다른데서 쓸 수 있도록 복구
                
n = 3

a = [i for i in range(1,n+1)]

p = [0] * n

used = [0] * n

permutation(0,3)

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

 

빈 배열 p에 원소를 하나씩 채워 넣으면서 순열을 완성하는 방법이다

 

i = 0일 때 p의 0번째 원소를 먼저 채워넣는다

 

j는 for j in range(3)을 순회하므로 0부터 2까지 가능하다

 

먼저 j=0인데 used[j]가 0인지 아닌지 체크한다

 

0이므로 a[j] = a[0]을 p[0]에 넣고, used[0] = 1로 바꾼다

 

 

 

다시 i +1 = 1로 이동해서, for j in range(3):을 순회하면... j=0에서 used[0] = 1이므로 넘어가고

 

used[1] = 0이므로 a의 1번 원소를 사용하여 p[1]에 넣는다

 

그리고 used[1] = 1로 바꾸고 i + 1 = 2로 이동한다

 

 

다음 i+1=2으로 이동해서 for j in range(3):을 순회하는데 used[0], used[1]은 1이므로 used[2]는 0인 a의 2번 원소를 사용하여 p[2]에 채워넣자

 

그러면 p = [1,2,3]의 하나의 순열이 완성된다

 

i+1=3으로 이동하면 r=3과 같으므로 p를 출력한다

 

그 후 재귀적 반복을 수행..

 

 

4. 중복순열1

 

그러면 중복순열은 어떻게 만들까?? used 배열을 이용한 위 과정을 조금 응용해보면..

 

used가 이전 과정에서 사용한 원소를 사용하지 못하게 만드는거잖아

 

그러면 used를 쓰지 않으면..? 사용한 원소를 또 사용할 수 있으니까 중복순열이 되겠지

 

def permutation_with_repetition(i,r):
    
    if i == r:
        
        print(p)
    
    else:
        
        for j in range(r):
            
            p[i] = a[j]
            
            permutation_with_repetition(i+1,r)

n = 3

a = [i for i in range(1,4)]

p = [0] * n

permutation_with_repetition(0,n)

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]

 

 

5. n개 중에서 r개를 고르는 순열

 

때로는 배열의 원소가 n개일때 일부분 r개만 사용한 순열을 얻고 싶을 수 있다

 

결정해야할 index i가 r이 될때까지만 순열을 채워넣으면 된다

 

def nPr(i,n,r):
    
    if i == r: ##r번이 될때까지만 순열을 채워넣는다
        
        print(p)
    
    else:
        
        for j in range(n):
            
            if used[j] == 0: ##a[j]가 사용되지 않았으면
                
                p[i] = a[j] ##i번째에 a[j]를 사용하여 채워넣고
                
                used[j] = 1  ##a[j]를 사용했다고 표시
                
                nPr(i+1,n,r)  ##p[i+1]을 결정하러 이동
                
                used[j] = 0  ##a[j]를 다른 자리에서 쓸 수 있도록 만들기

n = 4

r = 2

a = [i for i in range(1,n+1)]

used = [0] * n

p = [0] * r

nPr(0,n,r)

[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]

 

 

6. n개중에서 r개를 고르는 중복순열

 

위에서 했던 응용 그대로 used를 사용하지 않으면 중복순열이 된다

 

def nPr_repetition(i,n,r):
    
    if i == r:
        
        print(p)
    
    else:
        
        for j in range(n):
            
            p[i] = a[j]
            
            nPr_repetition(i+1,n,r)


n = 4

r = 2

a = [i for i in range(1,n+1)]

p = [0] * r

nPr_repetition(0,n,r)

[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 4]

 

 

7. 특정한 위치를 고정시키고 순열을 구하는 방법?

 

[1,2,3,4,5]에서

 

맨 앞자리가 1이면서 길이가 3인 순열을 구하고 싶다면 어떻게 해야할까

 

순열 배열 p = [0]*3에서 앞자리 p[0] = 1로 고정하고, used[0] = 1로 0번의 1은 사용했다고 만든다

 

그 다음에 0번은 결정시켰으므로 i=1부터 시작하도록 permutation(1,n,r)을 사용

 

def permutation(i,n,r):
    
    if i == r:
        
        print(p)
    
    else:
        
        for j in range(n):
            
            if used[j] == 0:
                
                used[j] = 1
                
                p[i] = a[j]
                
                permutation(i+1,n,r)
                
                used[j] = 0

n = 5
r = 3

a = [i for i in range(1,n+1)]

p = [0]*r
used = [0] * n

##앞자리가 1인 순열

p[0] = 1
used[0] = 1

permutation(1,n,r)
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 2]
[1, 3, 4]
[1, 3, 5]
[1, 4, 2]
[1, 4, 3]
[1, 4, 5]
[1, 5, 2]
[1, 5, 3]
[1, 5, 4]

##앞자리가 2인 순열

p[0] = 2
used[1] = 1 ##1번 원소인 2를 사용했다

permutation(1,n,r)
[2, 1, 3]
[2, 1, 4]
[2, 1, 5]
[2, 3, 1]
[2, 3, 4]
[2, 3, 5]
[2, 4, 1]
[2, 4, 3]
[2, 4, 5]
[2, 5, 1]
[2, 5, 3]
[2, 5, 4]

 

그러면 1번 자리가 3인 순열 이런것도 만들 수 있나??

 

그러면 함수를 좀 바꿔야할듯

 

1번 자리를 건들지 말도록 fixed 시키는 장치를 마련해야할것 같은데

 

def permutation(i,n,r,f):
    
    if i == r:
        
        print(p)
    
    else:
        
        for j in range(n):
            
            if i == f: ##i가 고정시킨 f라면..
                
                i = i + 1 ##그냥 i에 1을 더해서 그 자리는 건너 뛴다
            
            if used[j] == 0:
                
                used[j] = 1

                p[i] = a[j]

                permutation(i+1,n,r,f)

                used[j] = 0

n = 5

r = 3

a = [i for i in range(1,n+1)]

used = [0] * n

p = [0] * r

p[1] = 3
used[2] = 1

permutation(0,n,r,1)
                
                
[1, 3, 2]
[1, 3, 4]
[1, 3, 5]
[2, 3, 1]
[2, 3, 4]
[2, 3, 5]
[4, 3, 1]
[4, 3, 2]
[4, 3, 5]
[5, 3, 1]
[5, 3, 2]
[5, 3, 4]