[Function] Generate permutations in lexicographic order

[kon]

[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]

@KON
that's very nice!!
i am trying to edit so that i get the index also of any number
Thanks for posting this

[smorgasbord]

@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
    }

[kon]

@smorgasbord Thanks for taking the time to look at this thread and comment.

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

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.

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]

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

[MasterFocus]

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)

[smorgasbord]

@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

[Avi]

Related: UniquePmt and SM_UniquePMT()

[Avi]

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]

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.