Note also: these functions are published under the WTFPL v2
What is a permutation?
A permutation is a re-ordering of a set, such as (1,2,3) , (1,3,2) , (2,1,3) ...
A lexicographic permutation is a special type which involves the order of the set. The next lexicographic permutation of '32541' is '34125'. Numerically, it is simply the smallest set larger than the current one. This technique also works when there are repeated numbers; the next lexicographic permutation of '32127' is '32172'.
What do these functions do?
I'm providing one function which works on characters (suitable for numbers and permutations of words) and one which works on arrays (AHK_L required) within the following examples:
Strings:
#NoEnv StringCaseSense On o := str := "adimn" ; You will see my name 'nimda' near the bottom of the permutations list Loop { str := perm_next(str) If !str { MsgBox % o break } o.= "`n" . str } perm_Next(str){ p := 0, sLen := StrLen(str) Loop % sLen { If A_Index=1 continue t := SubStr(str, sLen+1-A_Index, 1) n := SubStr(str, sLen+2-A_Index, 1) If ( t < n ) { p := sLen+1-A_Index, pC := SubStr(str, p, 1) break } } If !p return false Loop { t := SubStr(str, sLen+1-A_Index, 1) If ( t > pC ) { n := sLen+1-A_Index, nC := SubStr(str, n, 1) break } } return SubStr(str, 1, p-1) . nC . Reverse(SubStr(str, p+1, n-p-1) . pC . SubStr(str, n+1)) } Reverse(s){ Loop Parse, s o := A_LoopField o return o }
Objects:
#NoEnv StringCaseSense On obj := [1, 3, 20, 52.5], output := ObjDisp(obj) Loop { obj := perm_NextObj(Obj) If !obj { MsgBox % output break } output .= "`n" ObjDisp(obj) } perm_NextObj(obj){ p := 0, objM := ObjMaxIndex(obj) Loop % objM { If A_Index=1 continue t := obj[objM+1-A_Index] n := obj[objM+2-A_Index] If ( t < n ) { p := objM+1-A_Index, pC := obj[p] break } } If !p return false Loop { t := obj[objM+1-A_Index] If ( t > pC ) { n := objM+1-A_Index, nC := obj[n] break } } obj[n] := pC, obj[p] := nC return ObjReverse(obj, objM-p) } ObjReverse(Obj, tail){ o := ObjClone(Obj), ObjM := ObjMaxIndex(O) Loop % tail o[ObjM-A_Index+1] := Obj[ObjM+A_Index-tail] return o } ObjDisp(obj){ s := "[" For k, v in obj s .= v ", " return SubStr(s, 1, strLen(s)-2) . "]" }
Here is sample output for the second when the array is initialised to [10, 20, 30, 400]:
[10, 20, 30, 400] [10, 20, 400, 30] [10, 30, 20, 400] [10, 30, 400, 20] [10, 400, 20, 30] [10, 400, 30, 20] [20, 10, 30, 400] [20, 10, 400, 30] [20, 30, 10, 400] [20, 30, 400, 10] [20, 400, 10, 30] [20, 400, 30, 10] [30, 10, 20, 400] [30, 10, 400, 20] [30, 20, 10, 400] [30, 20, 400, 10] [30, 400, 10, 20] [30, 400, 20, 10] [400, 10, 20, 30] [400, 10, 30, 20] [400, 20, 10, 30] [400, 20, 30, 10] [400, 30, 10, 20] [400, 30, 20, 10]Note that the final permutation is the array in descending order (reversed from the start.)
Finding the next permutation happens in O(1) time, since generating all permutations is O(n log n) time. This approach is suitable for large sets, since the set is held in O(n) memory, permutations are generated one at a time, and no recursion is used.