Next Permutation

implement next

permutation, which rearranges numbers into the lexicographically next greater

permutation of numbers.

if such

arrangement is not possible, it must rearrange it as the lowest possible order

(ie, sorted in ascending order).

the

replacement must be in-place, do not allocate extra memory.

here

are some examples. inputs are in the left-hand column and its corresponding

outputs are in the right-hand column.

<code>1,2,3</code> → <code>1,3,2</code>

<code>3,2,1</code> → <code>1,2,3</code>

<code>1,1,5</code> → <code>1,5,1</code>

思路：下一個排列，主要依靠字典序來排列的。首先，從最尾端開始往前尋找兩個相鄰元素，滿足num[i]&lt;num[i+1],記錄i，找到這樣的一組相鄰元素，再從最尾端往前查找，找出第一個大于num[i]的元素，索引記為j。将num[i]和num[j]對調，然後将i+1後的所有元素調到排列。記為“下一個”排列組合。