[Algorithm] combinatories/permutation/next-permutation-generator

문제 설명

n개의 구별 가능한 요소에 의해 만들어진 n!의 perm 집합이 있다.
그 집합을 오름차순으로 정렬한다.
그 집합의 한 원소를 input으로 넣으면 다음 차례의 perm을 반환하는 함수를 작성하여라

디테일

1. function prototype : def solution(n, prevperm)
2. when n = 4, prevperm = [], function return [0,1,2,3]
3. when n = 4, prevperm = [0,1,2,3], function return [0,1,3,2]
4. when n = 4 prevperm = [3,2,1,0], function return []

주저리

어디선가 풀어본 문제
그렇지만 머리에 확실하게 남아있지 않은 문제
그래서 이 공간에 확실하게 기록하여 내 머리 속에 각인시키고 싶은 문제

접근법

코드

def next_perm_gen(n, preperm):
    if len(preperm) == 0:
        return [e for e in range(n)]
    for i in range(n-1, 0, -1):
        if preperm[i-1] < preperm[i]:
            left = preperm[:i-1]
            standard = preperm[i-1]
            right=preperm[i:]
            pivot = min( [e if e>standard else n for e in right] )
            right.remove(pivot)
            right.append(standard)
            return left + [pivot] +sorted(right)

    return []