(파이썬) 순열 -모든 경우 나열하기

\(1, 2, 3, 4, 5\) 를 나열하는 순열의 수는 \(5!=120\) 가지로 금방 계산할 수 있지만, 실제로 \(120\) 를 나열하는 것은 사람이 하기 힘든 일이다. 컴퓨터로 하면 금방 될거라고 생각했는데, 생각만큼 쉽지는 않았다. 이런 저런 방법들을 생각해 보다가 결국 함수를 재귀적으로 사용하는 방법으로 결정을 했는데, 나열해야 하는 숫자가 많아질수록 시간이 좀 많이 걸리는 것 같다. 그래도 지금 수준에서 찾아낼 수있는 최선의 방법인거 같아 기록을 남긴다.

새로운 방법을 배우고야 말았다.  그래서 두 가지 방법을 모두 소개하기로 한다.

1. 재귀함수를 이용하는 방법

기본적인 아이디어는 간단한다.

1 한 개를 나열하는 방법은 당연히 (1) 한 가지다.

1, 2 두 개를 나열하는 방법은 맨 앞자리가 1인 경우 (1, 2) 밖에 없고, 맨 앞자리가 2인 경우 (2, 1) 밖에 없어서 두 가지다.

1, 2, 3 세 개를 나열하는 방법은 

     - 맨 앞 자리가 1인 경우 나머지 두 자리 (2, 3)을 나열하는 경우를 구하고

     - 맨 앞 자리가 2인 경우 나머지 두 자리 (1, 3)을 나열하는 경우를 구하고

     - 맨 앞 자리가 3인 경우 나머지 두 자리 (1, 2)를 나열하는 경우를 구하면 된다.

이 뒤로는 같은 방법으로 구한다.

파이썬으로 만들어보면 다음과 같다.

def perm(a):     # permutation을 얻어내기 위한 함수를 정의한다. 인수로는 나열해야할 숫자들을 리스트로 받는다.
    length=len(a)     # 나열해야할 리스트의 길이(개수)를 계산한다.
    if length==1:     # 만약 나열해야할 리스트에 원소가 1개 밖에 없다면 그냥 인수로 받았던 리스트를 반환한다.
        return [a]
    else:
        result=[]      # 결과가 저장 될 빈 리스트를 생성한다.
        for i in a:     # 리스트 a의 원소들을 하나씩 i에 받는다.
            b=a.copy()     # b에 인수로 받은 리스트를 복사한다.
            b.remove(i)     # 맨 앞자리에 i가 오는 경우 일단 b에서 i를 제거하고
            b.sort()     # i가 제거된 b를 오름차순으로 정렬한다.
            for j in perm(b):     # 함수를 재귀적으로 사용하여 b에 속한 원소들을 나열하는 순열의 모든 경우를 리스트로 받는다.
                j.insert(0, i)     # 다시 맨 앞자리에 i를 추가해 준다.
                if j not in result:     # result에 j 가 존재하지 않는다면 result에 j를 추가한다. 
                    result.append(j)     # 이렇게 하면 같은 것이 있는 순열의 모든 경우도 나열하는 것이 가능하다. 
    return(result)

위 함수의 아래에 사용자로부터 나열할 숫자들을 입력받아  결과를 보여주는 부분을 작성하면 다음과 같다. 

def perm(a):
    length = len(a)
    if length == 1:
        return [a]
    else:
        result = []
        for i in a:
            b = a.copy()
            b.remove(i)
            b.sort()
            for j in perm(b):
                j.insert(0, i)
                if j not in result:
                    result.append(j)
        return result


if __name__ == "__main__": 
    num = input('1부터 n까지 자연수를 나열하는 순열을 구합니다. n 을 입력하세요 : ')
    a = [x for x in range(1, int(num) + 1)]
    c = perm(a)
    for i in range(len(c)):
        print(i + 1, c[i])

이것을 실행하면 다음과 같다.

1부터 n까지 자연수를 나열하는 순열을 구합니다. n 을 입력하세요 : 4
1 [1, 2, 3, 4]
2 [1, 2, 4, 3]
3 [1, 3, 2, 4]
4 [1, 3, 4, 2]
5 [1, 4, 2, 3]
6 [1, 4, 3, 2]
7 [2, 1, 3, 4]
8 [2, 1, 4, 3]
9 [2, 3, 1, 4]
10 [2, 3, 4, 1]
11 [2, 4, 1, 3]
12 [2, 4, 3, 1]
13 [3, 1, 2, 4]
14 [3, 1, 4, 2]
15 [3, 2, 1, 4]
16 [3, 2, 4, 1]
17 [3, 4, 1, 2]
18 [3, 4, 2, 1]
19 [4, 1, 2, 3]
20 [4, 1, 3, 2]
21 [4, 2, 1, 3]
22 [4, 2, 3, 1]
23 [4, 3, 1, 2]
24 [4, 3, 2, 1]

2. 대소관계를 이용하는 방법

이름 붙이기가 애매 모호하여 일단 대소관계를 이용하는 방법이라고 했는데, 기본적인 생각은 다음과 같다.

1, 2, 3, 4 를 나열하는 방법은 이 네가지 숫자들로 만들 수 있는 네 자리 자연수의 개수와 같다고 할 수 있다.

즉, 1, 2, 3, 4 를 모두 사용하여 만들 수 있는 네 자리 자연수 중 가장 작은 1234 에서 부터 가장 큰 4321 까지를 오름차순으로 나열하면 순열의 모든 경우를 나열하는 것과 같다는 생각에서 출발하였다.

1234에서 부터 시작하여 1234보다 큰 바로 다음 자연수를 찾으면 된다.

생각해보면 1과 2는 그대로 두고 3, 4의 자리를 바꿔준 1243 이 다음으로 큰 자연수가 된다. 따라서 1243 을 순열의 결과에 추가한다.

이런 과정을 컴퓨터에게 어떻게 알려줘야 할까?

일단 일의 자리와 십의 자리를 비교하여 (일의 자리 수) > (십의 자리 수) 이면 두 수를 맞교환 한다고 생각하자.

1243 보다 큰 바로 다음 자연수 1324 라는 것을 찾는 것은 어렵지 않다.

그럼 컴퓨터에게는 어떤 절차를 알려주어 1324를 찾을 수 있게 해야 할까?

(일의 자리 수) < (십의 자리 수) 이므로 이 경우에는 십의 자리 수와 백의 자리 수를 비교한다.

(십의 자리 수) > (백의 자리 수) 이므로 백의 자리 수를 바꿔줘야 할 것 같은데, 단순히 백의 자리 수와 십의 자리수를 바꿔주면 안된다.

따라서 (십의 자리 수) > (백의 자리 수) 이면 십의 자리 수와 일의 자리 수 중 백의 자리 수인 2 보다는 크지만 가장 작은 수를 골라야 한다.

즉, 이 경우에는 4와 3이 2보다 크지만 3이 4보다는 작기 때문에 3이 선택되고, 3과 2의 자리를 바꿔줘야 한다. 

그래서 1342를 얻을 수 있다. 그렇지만 1342는 우리가 원했던 1324가 아니다. 

다라서 십의 자리 수와 일의 자리수를 오름차순으로 다시 정렬해야 한다. 즉, 4, 2를 오름차순으로 정렬하면 2, 4가 되기 때문에 최종적으로 우리가 얻는 수는 1324가 되는 것이다.

1324보다 큰 바로 다음 수는 1342가 될 것이고, 이는 (일의 자리 수) > (십의 자리 수) 이므로 이 두 숫자를 바꿔줌으로써 얻을 수 있다.

1342보다 큰 바로 다음 수는 1423이다. 이것도 같은 방식으로 얻어낼 수 있다.

(일의 자리 수) < (십의 자리 수) 이므로 다음 십의 자리 수와 백의 자리 수를 비교한다.

(십의 자리 수) > (백의 자리 수) 이므로 이제 십의 자리 수와 일의 자리 수 중 백의 자리 수인 3보다는 크지만 가장 작은 수를 골라야 한다.

2는 3보다 작고, 4는 3보다 크기 때문에 4를 선택한다. 그리고 두 숫자를 맞바꾸면 1432를 얻을 수 있다.

마지막으로 십의 자리 수와 일의 자리 수를 오름차순으로 정렬하면 1423을 얻을 수 있는 것이다.

1423보다 큰 바로 다음 수는 1432가 될 것이고, 이는 (일의 자리 수) > (십의 자리 수) 이므로 이 두 숫자를 바꿔줌으로써 얻을 수 있다.

1432보다 큰 바로 다음 수는 2134가 될 것이다. 이것 역시 같은 방식으로 얻어낼 수 있다.

(일의 자리 수) < (십의 자리수) 이므로 다음을 비교하고 (십의 자리 수) < (백의 자리 수) 이므로 다음을 비교한다.

(백의 자리 수) > (천의 자리 수) 이므로 백의 자리, 십의 자리, 일의 자리 수 중 천의 자리 수인 1보다는 크지만 가장 작은 수를 골라야 한다.

4, 3, 2 모두 1보다 크고 그 중 가장 작은 것이 2이기 때문에 2를 선택하여 둘의 자리를 바꿔주면 2431 이 된다.

마지막으로 백의 자리, 십의 자리, 일의 자리 수를 오름차순으로 정렬하면 2134 를 얻을 수 있다.

이런 식으로 계속 진행하여 가장 큰 수인 4321에 도달할 때까지 반복한다.

이 방법은 재귀함수를 이용하는 방법보다 훨씬 빠르게 순열의 모든 경우를 나열해 준다.

파이썬 코드는 다음과 같다.

def update(the_list, n, result):
    templist = the_list[n:]
    templist.sort()
    the_list = the_list[:n]+templist
    result.append(the_list.copy())
    return the_list


def perm(num):
    source = [x for x in range(1, int(num) + 1)]
    resource = [x for x in range(int(num), 0, -1)]
    result = [source.copy()]

    while source != resource:
        for i in range(len(source)-1, 0, -1):
            if source[i] > source[i-1]:
                for j in range(i, len(source)):
                    if source[i-1] > source[j]:
                        temp = source[i-1]
                        source[i-1] = source[j-1]
                        source[j-1] = temp
                        source = update(source, i, result)
                        break
                    elif j == len(source) - 1:
                        temp = source[i-1]
                        source[i-1] = source[j]
                        source[j] = temp
                        source = update(source, i, result)
                        break
                break
    return result

if __name__ == "__main__":
    num = input("1 부터 n 까지 자연수를 나열하는 순열을 구합니다. n 을 입력하세요 : ")
    final = perm(num)
    for i in range(len(final)):
        print(i + 1, final[i])

이 코드를 실행해도 같은 결과를 얻게 된다.

위 두 가지 방법이 n=4 일 때는 실행시간에 별 차이가 없지만 n=8 일 때 부터는 현저한 차이를 보이게 된다. 두 번째 방법이 훨씬 더 빠르게 결과를 보여준다.

`