next_permutations, prev_permutation, k permutations

https://www.huangwenchao.com.cn/2015/05/python-permutation.html

쓸일이 많을것같아서 저장. 파이썬의 itertools모듈에 permutations가 있지만 다음거 구하는게 없이

전부 다 구하는거다. 종종 다음 permutations가 필요할 때가 있는데 그때를 위해 저장.

# -*- encoding: cp949 -*-
def next_permutation(a):
    if len(a) < 2: return False
    i = len(a)-2
    while i >= 0 and a[i] >= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1
    k = len(a) - 1
    while a[i] >= a[k]: k -= 1
    (a[i], a[k]) = (a[k], a[i])
    a[j:] = a[:j-1:-1]
    return a

def prev_permutation(a):
    if len(a) < 2: return False
    i = len(a)-2
    while i >= 0 and a[i] <= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1
    k = len(a) - 1
    while a[i] <= a[k]: k -= 1
    (a[i], a[k]) = (a[k], a[i])
    a[j:] = a[:j-1:-1]
    return a

print next_permutation([4,5,4]) #다음 순열이 없으면 False 리턴, 있으면 순열 리턴.
print prev_permutation([4,5,4])

n번째 순열 구하기.

# -*- encoding: cp949 -*-
from math import factorial, floor
def kthperm(S, k):  #  nonrecursive version
    P = []
    while S != []:
        f = factorial(len(S)-1)
        i = int(floor(k/f))
        x = S[i]
        k = k%f
        P.append(x)
        S = S[:i] + S[i+1:]
    return P

n=input()
print kthperm([1,2,3,4],n-1)