다음 순열-next_purmutations(Biggest is greater)

다음 순열-next_purmutations

 

파이썬에서 순열에 대한 라이브러리는 제공하지만 다음 순열값을 불러오는 것에 대해서는 제공하지 않는다. 

순열은 서로 다른 n개에 집합에서 r개를 순서있게 나열하는 것이다.

 

보통 알고리즘 문제에서는

1) a,b,d,e 다음에 나올 최솟값은 무엇이 나오는가? 

2) 1,2,4,3,5 다음에 나올 최솟값은 무엇인가? 

로 볼 수 있다. 

 

필자는 해커랭크 문제에서 해당 알고리즘의 필요성을 느꼈다.

https://www.hackerrank.com/challenges/bigger-is-greater/problem?isFullScreen=true 

Bigger is Greater | HackerRank

 

next_permutations 코드. 

s = list(input())

def next_permutations(arr):
  i,j = len(arr)-1, len(arr)-1

  #증가하는 형태를 찾을때까지
  while i>0 and arr[i-1]>=arr[i]:
    i-=1
  if i==0:
    return False
  while arr[i-1]>=arr[j]:
    j-=1
  arr[i-1], arr[j] = arr[j], arr[i-1]

  k = len(arr)-1
  #엇갈릴떄까지
  while i<k:
    arr[i],arr[k] = arr[k],arr[i]
    i+=1
    k-=1
  return arr

print(next_permutations(s))

 

이 함수는 arr의 값이 int가 오든 char타입이 오든 상관하지 않고 순열을 진행한다. 역시 파이썬은 범용성이 넓다.

 

if i==0 부분은 다음 순열을 반환하는 패턴을 찾을 수 없을 때 False를 리턴한다.

 

당연하면서 재밌는 사실이있는데

맨 마지막 i와 k를 계속해서 swap해주는 이유는 수의 열이 감소하는 형태일때 대칭적으로 swap한다면 sort하는 형태를 띄게 되기 때문이다.