Next Lexicographical Permutation

# 辞書順で直後の順列を求めたい

長さ$n$の配列から$n$個の要素を取り出す順列を考える．ある並びを与えられたときに，順列を辞書順に並べたときの直後の並びを求めたい．

1
2
[0, 1, 2, 3] -> [0, 1, 3, 2]
[0, 1, 2, 5, 3, 3, 0] -> [0, 1, 3, 0, 2, 3, 5]

# 答え

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def next_permutation(lst):
    i = len(lst) - 1
    while 0 < i and lst[i-1] >= lst[i]:
        i -= 1
    if i == 0:
        return lst.reverse()
    i -= 1
    pivot = lst[i]
    j = len(lst) - 1
    while pivot >= lst[j]:
        j -= 1
    lst[i], lst[j] = lst[j], lst[i]
    lst[i + 1:] = reversed(lst[i + 1:])
    return lst

ref: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm