動機

詳細的可以看Algorithm, Leetcode-31

步驟

  1. 找合法的升序或降序到哪
  2. 把前一個數字換到這個序列
  3. reverse這序列

next perm

def findStartOfRevOrder(arr):
    i = len(arr)-1 # start from the last index
    while i > 0 and arr[i-1] >= arr[i]:
        i -= 1
    return i if i > 0 else -1
def f(arr):
    i = findStartOfRevOrder(arr)-1
    while i >= 0:
        j = len(arr)-1
        while j >= 0 and arr[i] >= arr[j]: # keep the small ones in last AND skip the pos with the same digit
            j -= 1
        if j >= 0:
            # swap
            arr[i], arr[j] = [arr[j],arr[i]]
            arr[i+1:] = arr[i+1:][::-1] # keep big digit as the last
            i = findStartOfRevOrder(arr)-1
            yield arr
        else:
            break

prev perm

def findStartOfAscOrder(arr):
    i = len(arr)-1 # start from the last index
    while i > 0 and arr[i-1] <= arr[i]:
        i -= 1
    return i if i > 0 else -1
def g(arr):
    i = findStartOfAscOrder(arr)-1
    while i >= 0:
        j = len(arr)-1
        while j >= 0 and arr[i] <= arr[j]: # keep the small ones in last AND skip the pos with the same digit
            j -= 1
        if j >= 0:
            # swap
            arr[i], arr[j] = [arr[j],arr[i]]
            arr[i+1:] = arr[i+1:][::-1] # keep small digit as the last
            i = findStartOfAscOrder(arr)-1
            yield arr
        else:
            break