[leetcode][python][c]31. Next Permutation

這題雖然難度是中等，但想了好久才想到規則，因此紀錄一下


舉一個例子

[1,2,3] 的所有排列組合順序:

1. 1,2,3
2. 1,3,2
3. 2,1,3
4. 2,3,1
5. 3,1,2
6. 3,2,1 <=下一個又跳回第一組從小到大的組合

觀察變化可得知下列規則:

1. 從最後面開始數，找到上升的最大值(紅字)
1. 特例: 若最大值在第一個，代表是最後的組合，下一個應該變回第一個組合小至大
1. 只要依序swap第一個與最後一個，第二個與最後第二個....
2. 找出最大值左邊的數字(藍色)
3. 將藍色與右邊大於藍色的最小值swap
4. 將藍色右邊由小至大排序

最後就是應題目規定，只能allocate 固定的記憶體
因此須自己做in-place 的swap()  與sort()

source code:
https://github.com/cy-arduino/leetcode/blob/master/31.%20Next%20Permutation.py
https://github.com/cy-arduino/leetcode/blob/master/31.%20Next%20Permutation.c