動機
詳細的可以看Algorithm, Leetcode-31
步驟
- 找合法的升序或降序到哪
- 把前一個數字換到這個序列
- 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