## [Function] Generate permutations in lexicographic order

Post your working scripts, libraries and tools
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

### [Function] Generate permutations in lexicographic order

[Function] Generate permutations in lexicographic order
Find the next highest permutation of a number using the method described here: https://en.wikipedia.org/wiki/Permutati ... phic_order

Function and example:

Code: Select all

``````SetBatchLines, -1
n := 123456
while (n := NextLex(n))
MsgBox, % "The next permutation of n is " n "."
MsgBox, % "No more permutations."
return

NextLex(n)
{
a := []
Loop, Parse, n
a[A_Index] := A_LoopField

;Find the largest index k such that a[k] < a[k + 1].
;If no such index exists, the permutation is the last permutation.
Loop % a.MaxIndex() - 1
{
if (a[A_Index] < a[A_Index + 1])
k := A_Index
}
if (!k)
return, 0

;Find the largest index l such that a[k] < a[l].
Loop % a.MaxIndex() - k
{
if (a[k] < a[A_Index + k])
l := A_Index + k
}

;Swap the value of a[k] with that of a[l].
Temp := a[k]
a[k] := a[l]
a[l] := Temp

;Reverse the sequence from a[k + 1] up to and including the final element a[n].
Loop, % a.MaxIndex() - k
Temp%A_Index% := a[A_Index + k]
Loop, % a.MaxIndex() - k
a[a.MaxIndex() - A_Index + 1] := Temp%A_Index%

for key, val in a
r .= val
return, r
}``````
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

### Re: [Function] Generate permutations in lexicographic order

@KON
that's very nice!!
i am trying to edit so that i get the index also of any number Thanks for posting this John ... you working ?
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

### Re: [Function] Generate permutations in lexicographic order

@Kon
Tweaked your code a bit just 2-3 lines, btw: in your code i guess it does not support any number with zero(es) in it

Code: Select all

``````    SetBatchLines, -1
/*
index := 2
array =
(
112, 211
)

StringSplit,  hello, array, `,
n := hello1
n3 := n
n2 := hello2
;MsgBox % hello0
*/
InputBox, array, Enter A number a comma and then its nth permutatation no., **no zeroes**
; MsgBox %array%
index := 2

StringSplit,  hello, array, `,
n := hello1
n3 := n
n2 := hello2

;MsgBox %n% and %n2%

while (n := NextLex(n))
{
if ( n2 = n )
MsgBox, % "The " index "th  permutation of " hello1 " is "  n2 " ."
index := index + 1
}
MsgBox, % "No more permutations."
return

NextLex(n)
{
a := []
Loop, Parse, n
a[A_Index] := A_LoopField

;Find the largest index k such that a[k] < a[k + 1].
;If no such index exists, the permutation is the last permutation.
Loop % a.MaxIndex() - 1
{
if (a[A_Index] < a[A_Index + 1])
k := A_Index
}
if (!k)
return, 0

;Find the largest index l such that a[k] < a[l].
Loop % a.MaxIndex() - k
{
if (a[k] < a[A_Index + k])
l := A_Index + k
}

;Swap the value of a[k] with that of a[l].
Temp := a[k]
a[k] := a[l]
a[l] := Temp

;Reverse the sequence from a[k + 1] up to and including the final element a[n].
Loop, % a.MaxIndex() - k
Temp%A_Index% := a[A_Index + k]
Loop, % a.MaxIndex() - k
a[a.MaxIndex() - A_Index + 1] := Temp%A_Index%

for key, val in a
r .= val
return, r
}``````
John ... you working ?
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

### Re: [Function] Generate permutations in lexicographic order

@smorgasbord Thanks for taking the time to look at this thread and comment.
smorgasbord wrote:@Kon
Tweaked your code a bit To do what?
Just to be clear, you "tweaked" the example, not the function. Are you suggesting I should add more examples of ways to use the function?
smorgasbord wrote:

Code: Select all

``InputBox, array, Enter A number a comma and then its nth permutatation no., **no zeroes**``
From the looks of your example, you are not asking the user to input the "nth permutatation no.". Instead you are asking them to input the nth permutation, then the code you wrote finds the nth permutation no.
smorgasbord wrote:btw: in your code i guess it does not support any number with zero(es) in it
The function does support the use of zeros. Can you provide an example of what you are describing so I can replicate this behavior?

By the way, what's with all the commented out code?
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

### Re: [Function] Generate permutations in lexicographic order

@kon
First and Second
I wanted something like this, input = 231,321
result
1.123
2.132
3.213
4.231
5.312
6.321
editing:
about Zeroes: Since the script starts indexing from 231 instead of 123 as shown above, i miss-calculated, your function is fine. could you add that above?
John ... you working ?
MasterFocus
Posts: 146
Joined: 01 Oct 2013, 09:47
GitHub: MasterFocus
Location: Rio de Janeiro - RJ - Brasil
Contact:

### Re: [Function] Generate permutations in lexicographic order

For the sake of sharing information, you can find many related stuff here:
http://www.autohotkey.com/board/topic/5 ... binations/
(see the "RELATED CONTENT" post)
Antonio França - git.io | github.com | ahk4.net | sites.google.com
Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.
Need help? Please post on the forum before sending me a PM.
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

### Re: [Function] Generate permutations in lexicographic order

@Master focus
+1 for the above, Thanks for making that please please since you are an admin/mod is it possible to see all maths related stuff at one particular place,
i requested the same on the old forums, there is so much significant info but it is all scattered. If it is all at one place any math buff would love that.

Btw: is the decimal to fraction converter complete, i guess it is please post that too John ... you working ?
Avi
Posts: 193
Joined: 30 Sep 2013, 09:51
GitHub: aviaryan
Location: India
Contact:

### Re: [Function] Generate permutations in lexicographic order

Last edited by Avi on 22 Oct 2013, 00:43, edited 1 time in total.
Avi
Posts: 193
Joined: 30 Sep 2013, 09:51
GitHub: aviaryan
Location: India
Contact:

### Re: [Function] Generate permutations in lexicographic order

smorgasbord wrote: Btw: is the decimal to fraction converter complete, i guess it is please post that too I tried something ...

Code: Select all

``````msgbox % dec2frac(4.44)
msgbox % dec2frac(999999.99)
return

/*
dec2frac(number)                    by Avi Aryan
Converts decimal to fraction

Returns >
space separated values of numerator and denominator
*/

dec2frac(number){
if !( dec_pos := Instr(number, ".") )
return number

n_dec_digits := Strlen(number) - dec_pos , dec_num := Substr(number, dec_pos+1)
, base_num := Substr(number, 1, dec_pos-1)

t := 1
loop % n_dec_digits
t .= "0"

numerator := base_num*t + dec_num , denominator := t
HCF := GCD(numerator, denominator)
numerator /= HCF , denominator /= HCF

return Round(numerator) " " Round(denominator)
}

/*
GCD(a,b)           BY Lazzlo

a = first number
b = second number

Returns >
the Greatest Common Divisor/Highest common factor of the two numbers
*/

GCD(a,b) {
Return b=0 ? Abs(a) : GCD(b, mod(a,b))
}
``````
The code resides in Math-Functions lib.
MasterFocus
Posts: 146
Joined: 01 Oct 2013, 09:47
GitHub: MasterFocus
Location: Rio de Janeiro - RJ - Brasil
Contact:

### Re: [Function] Generate permutations in lexicographic order

The current version of my FloatToFraction() function can be found here: www.autohotkey.com/board/topic/86320-floattofraction
I will upload any modifications I eventually make in a few weeks, when I (hopefully) get some time.
Antonio França - git.io | github.com | ahk4.net | sites.google.com
Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.
Need help? Please post on the forum before sending me a PM.