프로젝트 오일러 24번 - Lexicographic permutations

 

두가지정도로 해결할수 있는데, 첫번째는 직관적으로 숫자를 한자리씩 올려가며 100만번까지 순열을 만들어 내면서 계산하는 방법이고, 두번째는 진법 변환하듯이 각자릿수의 크기로 나누어서 구하는 방법입니다. 두번째 방법으로 하면 굳이 프로그래밍을 하지 않아도 될것 같네요. 일단 첫번째 방법만 해보도록 하겠습니다.

 

 

루프문 만들기

첫번째 수인 0123456789 부터 백만까지 루프문을 만듭니다. range에는 100만이 포함이 안되서, 실제로는 999,999 개이지만, 시작하는 숫자가 첫번째이기 때문에, 출력결과는 100만번째수입니다.

def get_next_permutation(string):
    #code here
    return number
    
string='0123456789'
for i in range(1,1000000):    
    string = get_next_permutation(string)
print(string)

 

함수부분

함수를 만들기 전에 순열의 패턴을 보면,

0123456789  # 제일 작은수. 다음수는 맨 오른쪽의 8과 9를 교환

0123456798  # 98은 최대값이므로, 앞의 7과 8을 교환하고, 7과 9는 최소가 되도록 79 로 정렬.

0123456879  # 맨 오른쪽끝의 7과 9를 교환

0123456897  # 97은 최대로 올라가있으므로, 왼쪽8을 9와 교환후, 7과8은 최소가 되도록 78로 정렬.

0123456978 #

0123456987

...

마지막 숫자 다음에 올숫자는

0123457689 입니다.  위 마지막숫자에서 끝세자리 987은 이미 최대로 자리가 올라가 있으므로, 그앞에 있는 6이 숫자가 올라가야 되고, 새로운 수는 오른쪽에 있는 수 중에서 그다음으로 큰수인 7입니다.(오른쪽에 7이 없으면 8이나 9가 될수도 있습니다.)

7을 6자리에 넣고, 남은 698 을 오름차순으로 정렬해서 689를 만들어서 뒷부분에 붙입니다.

이것을 코드로 표현하면 아래와 같습니다.

def get_next_permutation(string):
    i=len(string)-2
    while i >= 0:
        if string[i] < string[i+1]:
            target = sorted(string[i:])
            new_num = target.pop(target.index(string[i])+1)
            last_nums = ''.join(target)
            return string[:i] + new_num + last_nums
        i-=1

string[i]가 6이되고, string[i:] = '6987'이 되고, sorted()로 정렬을 하면, ['6','7','8','9']의 리스트가 생성이 되서, target에 저장이 됩니다. 그리고 target에서 6 의 위치(index)를 계산하고, 1을 더하면, 7이 나오고, 그 7을 target.pop(index) 로 뽑아내서 new_num 에 저장을 합니다. 이때 pop 을 하면, 뽑아내고 남은 target에서는 7이 삭제가 되서, 자동으로 ['6','8','9'] 만 남아서, 마지막 줄에서 ''.join으로 합쳐주기만 하면 됩니다.

 

def get_next_permutation(string):
    i=len(string)-2
    while i >= 0:
        if string[i] < string[i+1]:
            target = sorted(string[i:])
            new_num = target.pop(target.index(string[i])+1)
            last_nums = ''.join(target)
            return string[:i] + new_num + last_nums
        i-=1

string='0123456789'
for i in range(1,1000000):    
    string = get_next_permutation(string)
print(string)

 

추가)

위 함수는 숫자의 자릿수가 고정된 상태에서만 사용가능합니다. '0123456789' 처럼요.

만약, '4321' 에서 '12345' 처럼 자릿수가 올라가는 순열을 만들고 싶으시면 아래함수를 사용하세요.(41번 문제)

def get_next_permutation(string):
    for i in range(len(string)-1,0,-1):
        if string[i-1] < string[i]:
            target = sorted(string[i-1:])
            new_num = target.pop(target.index(string[i-1])+1)
            last_nums = ''.join(target)
            return string[:i-1] + new_num + last_nums
    if len(string)<9:
        return ''.join(sorted(string+str(len(string)+1)))