[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

12 Oct 2013, 15:10

[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
}
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: [Function] Generate permutations in lexicographic order

14 Oct 2013, 09:43

@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 ?
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: [Function] Generate permutations in lexicographic order

14 Oct 2013, 10:18

@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

14 Oct 2013, 14:25

@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?
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: [Function] Generate permutations in lexicographic order

15 Oct 2013, 04:58

@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 ?
User avatar
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

15 Oct 2013, 15:37

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.
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: [Function] Generate permutations in lexicographic order

15 Oct 2013, 22:19

@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 ?
User avatar
Avi
Posts: 193
Joined: 30 Sep 2013, 09:51
Facebook: avi.aryan.ap
Google: +AviAryan
GitHub: aviaryan
Location: India
Contact:

Re: [Function] Generate permutations in lexicographic order

22 Oct 2013, 00:27

Last edited by Avi on 22 Oct 2013, 00:43, edited 1 time in total.
Writes at Dev Letters

Clipjump Clipboard Manager : More Scripts (updated 2019)

Image
User avatar
Avi
Posts: 193
Joined: 30 Sep 2013, 09:51
Facebook: avi.aryan.ap
Google: +AviAryan
GitHub: aviaryan
Location: India
Contact:

Re: [Function] Generate permutations in lexicographic order

22 Oct 2013, 00:40

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.
Writes at Dev Letters

Clipjump Clipboard Manager : More Scripts (updated 2019)

Image
User avatar
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

22 Oct 2013, 02:21

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.

Return to “Scripts and Functions”

Who is online

Users browsing this forum: No registered users and 17 guests