Has anybody released any good functions for calculating the number of combinations/permutations for the following:
- combinations (without repetition)
- combinations with repetition
- permutations (without repetition)
- permutations with repetition
Or are there any relevant MSDN functions available?
I have written functions both to calculate the numbers (what I'm asking for), and to generate lists of combinations/permutations, however they are very complicated and dependent on other functions, so I would be interested in any alternative approaches. Thanks. (I will release them soon.)
==================================================
Some related links:
[started by wolf_II]
Permutations() - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=6&t=34230
Anagrams - AutoHotkey Community
https://autohotkey.com/boards/viewtopic ... 19&t=34240
[started by littlegandhi1199]
Anagram Solver by Littlegandhi1199 - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=5&t=34082
(Scrabble) Anagram Solver N/4-15 - AutoHotkey Community
https://autohotkey.com/boards/viewtopic ... 19&t=34285
==================================================
E.g.
'who's in the photo' (order doesn't matter)
combinations: 'aab' and 'baa' are equivalent
combinations with repetitions (10): aaa,aab,aac,abb,abc,acc,bbb,bbc,bcc,ccc
combinations with no repetitions (1): abc
'how are the people in the photo lined up' (order matters)
permutations: 'aab' and 'baa' are not equivalent
permutations with repetitions (27): aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc
permutations with no repetitions (6): abc,acb,bac,bca,cab,cba
I'm looking to get those numbers: 10, 1, 27, 6, I'm not concerned about generating the lists.
==================================================
Part of the difficulty with calculation, is that you quickly reach numbers above what AutoHotkey can handle. The formulas typically use factorial, for example, 20! can be handled by AutoHotkey, but not 21!. E.g. 5! = 5*4*3*2*1 = 120. So I've had to use workarounds, like listing the prime factors of two different numbers, and cancelling them out, before applying a calculation.
One reason you'd want to know the numbers, is to calculate how much space will be required to store the list.
==================================================
COMBINATIONS (WITHOUT REPETITION) (N CHOOSE K):
Excel: COMBIN(n,k)
when k <= n: n! / (k!(n-k)!)
when k > n: 0
e.g. Fact(3) / (Fact(3)*Fact(3-3)) = 1
COMBINATIONS WITH REPETITION:
Excel: COMBIN(n+k-1,k)
Excel: FACT(n+k-1) / (FACT(n-1)*FACT(k))
when applicable: (n+k-1)! / (k!(n-1)!)
e.g. Fact(3+3-1)/(Fact(3-1)*Fact(3)) = 10
PERMUTATIONS (WITHOUT REPETITION):
Excel: PERMUT(n,k)
when k <= n: n! / (n-k)!
when k > n: 0
e.g. Fact(3) / Fact(3-3) = 6
PERMUTATIONS WITH REPETITION:
Excel: k^n
when applicable: k^n
e.g. 3**3 = 27
combinations and permutations (and anagrams)
combinations and permutations (and anagrams)
Last edited by jeeswg on 14 Jul 2017, 15:57, edited 4 times in total.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations
I have this one ready to post:
I keep the number somewhat small by dividing after each multiplication. This also keep them as integers, rather than floats.
Edit: deals with n<k
Edit2: added example from wikipedia
Code: Select all
; combinations with repetitions (10): aaa,aab,aac,abb,abc,acc,bbb,bbc,bcc,ccc
MsgBox, % Combine(3, 3) ; 10
;-------------------------------------------------------------------------------
Combine(n, k) { ; number of combinations with repetitions
;-------------------------------------------------------------------------------
Return, Choose(n + k - 1, k)
}
;-------------------------------------------------------------------------------
Choose(n, k) { ; return "n choose k", binomial coefficients
;-------------------------------------------------------------------------------
; calculate n! / [k! * (n-k)!]
;---------------------------------------------------------------------------
; number of combinations without repetitions
; e.g. 5 cards out of deck of 52 cards = Choose(52, 5)
;---------------------------------------------------------------------------
Result := (n >= k) ; return zero for n < k
While n > k {
Result *= n--
Result /= A_Index
}
Return, Result
}
Edit: deals with n<k
Edit2: added example from wikipedia
Last edited by wolf_II on 13 Jul 2017, 04:18, edited 2 times in total.
Re: combinations and permutations
Maybe what would be better than looking at the prime factors, would be some big number functions, that do maths via string manipulation. Or possibly some Winapi functions for big numbers.
I.e. if I'm going to be manipulating strings (i.e. lists of factors), I might as well be manipulating strings with general-purpose 'big numbers' functions, instead of esoteric functions.
[EDIT:] This is a great library:
Scientific Maths - infinite precision Mathematics Library - Scripts and Functions - AutoHotkey Community
https://autohotkey.com/board/topic/9351 ... s-library/
autohotkey-scripts/Maths.ahk at master · aviaryan/autohotkey-scripts · GitHub
https://github.com/aviaryan/autohotkey- ... /Maths.ahk
What could be good is some external tool, so that I can verify the calculations in this library and in any custom big number functions that I make.
For manual checking, there is the Wolfram Alpha website.
Wolfram|Alpha: Computational Knowledge Engine
http://www.wolframalpha.com/
Using Excel for testing:
I.e. if I'm going to be manipulating strings (i.e. lists of factors), I might as well be manipulating strings with general-purpose 'big numbers' functions, instead of esoteric functions.
[EDIT:] This is a great library:
Scientific Maths - infinite precision Mathematics Library - Scripts and Functions - AutoHotkey Community
https://autohotkey.com/board/topic/9351 ... s-library/
autohotkey-scripts/Maths.ahk at master · aviaryan/autohotkey-scripts · GitHub
https://github.com/aviaryan/autohotkey- ... /Maths.ahk
What could be good is some external tool, so that I can verify the calculations in this library and in any custom big number functions that I make.
For manual checking, there is the Wolfram Alpha website.
Wolfram|Alpha: Computational Knowledge Engine
http://www.wolframalpha.com/
Using Excel for testing:
Code: Select all
q::
oXl := Excel_Get()
vN := 3, vK := 3
vOutput .= Round(oXl.WorksheetFunction.Combin(vN, vK)) "`r`n"
vOutput .= Round(oXl.WorksheetFunction.Combin(vN+vK-1, vK)) "`r`n"
vOutput .= Round(oXl.WorksheetFunction.Permut(vN, vK)) "`r`n"
vOutput .= vK**vN
MsgBox, % vOutput
oXl := ""
return
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations
I used in the past preccalc (32/64 bit versions available) from http://petr.lastovicka.sweb.cz/others.html#pijeeswg wrote:What could be good is some external tool, so that I can verify the calculations in this library and in any custom big number functions that I make.
Re: combinations and permutations (and anagrams)
I have some functions for calculating the number of, and generating lists of combinations/permutations (with/without repetitions).
Code: Select all
q:: ;combinations/permutations (with/without repetition)
;options
vOrig := "abc"
;vOrig := "abA"
;vOrig := "Aa"
;vOrig := "ab"
vCaseSen := 1
;vChoose := StrLen(vOrig)
vChoose := 3
;vChoose := 2
;vChoose := 1
vDiag := 0 ;diagnostic mode
if (vChoose > StrLen(vOrig))
{
MsgBox, % "warning: k > n"
return
}
;permutations (with repetition)
vOrigLF := RegExReplace(vOrig, "(?<=.)(?=.)", "`n") ;pad with LFs
vList := vOrigLF
vCaseSen ? (vSfxC := " C", vSfxCS := " CS") : (vSfxC := vSfxCS := "")
Loop, % vChoose - 1
{
vList := JEE_ListItemsPrepend(vOrigLF, vList, "`n")
if vDiag
MsgBox, % StrReplace(vList, "`n", ",") " " JEE_StrCount(vList "`n", "`n")
}
vList2 := JEE_ListItemsAlphabetise(vList, "`n", vSfxCS " st")
Sort, vList2, % "U" vSfxC
vCountPR := JEE_StrCount(vList "`n", "`n")
vCountCR := JEE_StrCount(vList2 "`n", "`n")
vOutput := "permutations with repetition: " vCountPR "`r`n" StrReplace(vList, "`n", ",") "`r`n`r`n"
vOutput .= "combinations with repetition: " vCountCR "`r`n" StrReplace(vList2, "`n", ",") "`r`n`r`n"
if vDiag
MsgBox, % vOutput
;permutations (without repetition)
vOrigLF := RegExReplace(vOrig, "(?<=.)(?=.)", "`n") ;pad with LFs
vList := vOrigLF
Loop, % vChoose - 1
{
vList := JEE_ListItemsPrepend(vOrigLF, vList, "`n")
if vDiag
MsgBox, % StrReplace(vList, "`n", ",") " " JEE_StrCount(vList "`n", "`n")
vList := JEE_StrGetSubwords(vOrig, vList "`n", vSfxCS)
if vDiag
MsgBox, % StrReplace(vList, "`n", ",") " " JEE_StrCount(vList "`n", "`n")
}
vList2 := JEE_ListItemsAlphabetise(vList, "`n", vSfxCS " st")
Sort, vList2, % "U" vSfxC
vCountP := JEE_StrCount(vList "`n", "`n")
vCountC := JEE_StrCount(vList2 "`n", "`n")
vOutput .= "permutations (without repetition): " vCountP "`r`n" StrReplace(vList, "`n", ",") "`r`n`r`n"
vOutput .= "combinations (without repetition): " vCountC "`r`n" StrReplace(vList2, "`n", ",") "`r`n`r`n"
vOutput .= vCountPR " " vCountCR " " vCountP " " vCountC "`r`n"
vN := StrLen(vOrig), vK := vChoose
vCountPR := JEE_Permut(vN, vK, "r")
vCountCR := JEE_Combin(vN, vK, "r")
vCountP := JEE_Permut(vN, vK)
vCountC := JEE_Combin(vN, vK)
vOutput .= vCountPR " " vCountCR " " vCountP " " vCountC "`r`n"
MsgBox, % vOutput
return
;==================================================
;JEE_Combin
;JEE_Permut
;(can handle larger numbers if include: SM_fact, SM_Multiply, SM_Divide, SM_Greater)
;JEE_Fact
;JEE_ListItemsAlphabetise
;JEE_ListItemsPrepend
;JEE_StrCount
;JEE_StrGetSubwords
;JEE_SortStable
;JEE_StrAlphabetise
;==================================================
;#Include, %A_ScriptDir%\Lib\Maths.ahk
;Scientific Maths - infinite precision Mathematics Library - Scripts and Functions - AutoHotkey Community
;https://autohotkey.com/board/topic/93516-scientific-maths-infinite-precision-mathematics-library/
;autohotkey-scripts/Maths.ahk at master · aviaryan/autohotkey-scripts · GitHub
;https://github.com/aviaryan/autohotkey-scripts/blob/master/Functions/Maths.ahk
;==================================================
JEE_Combin(vN, vK, vOpt="")
{
if InStr(vOpt, "r")
vN += vK - 1
if (vK > vN)
return 0
else if (vN <= 20) && (vK <= 12) && (vN-vK <= 12)
return Round(JEE_Fact(vN) / (JEE_Fact(vK)*JEE_Fact(vN-vK)))
else
{
SM_fact := "SM_fact", SM_Multiply := "SM_Multiply", SM_Divide := "SM_Divide", SM_Greater := "SM_Greater"
if !IsFunc(SM_fact)
return ""
vNum1 := %SM_Multiply%(%SM_fact%(vK), %SM_fact%(vN-vK))
vNum2 := %SM_Divide%(%SM_fact%(vN), vNum1)
if %SM_Greater%(vNum2, 9223372036854775807) ;0x7FFFFFFFFFFFFFFF
return vNum2
else
return vNum2+0
}
}
;==================================================
JEE_Permut(vN, vK, vOpt="")
{
if InStr(vOpt, "r")
return vK**vN
if (vK > vN)
return 0
else if (vN <= 20) && (vN-vK <= 20)
return Round(JEE_Fact(vN) / JEE_Fact(vN-vK))
else
{
SM_fact := "SM_fact", SM_Divide := "SM_Divide", SM_Greater := "SM_Greater"
if !IsFunc(SM_fact)
return ""
vNum := %SM_Divide%(%SM_fact%(vN), %SM_fact%(vN-vK))
if %SM_Greater%(vNum, 9223372036854775807) ;0x7FFFFFFFFFFFFFFF
return vNum
else
return vNum+0
}
}
;==================================================
;Scientific Maths - infinite precision Mathematics Library - Scripts and Functions - AutoHotkey Community
;https://autohotkey.com/board/topic/93516-scientific-maths-infinite-precision-mathematics-library/
;autohotkey-scripts/Maths.ahk at master · aviaryan/autohotkey-scripts · GitHub
;https://github.com/aviaryan/autohotkey-scripts/blob/master/Functions/Maths.ahk
;e.g.
;q::
vOutput := ""
Loop, 51
vOutput .= (A_Index-1) "`t" JEE_Fact(A_Index-1) "`r`n"
Clipboard := vOutput
MsgBox, % SubStr(vOutput, 1, -2)
return
;works for 0 <= vNum <= 20, and larger numbers if SM_fact exists
JEE_Fact(vNum)
{
if (vNum <= 20)
{
vOutput := 1
Loop, % vNum
vOutput *= A_Index
return vOutput
}
else if IsFunc("SM_fact") && (SM_fact := "SM_fact")
return %SM_fact%(vNum)
else
return ""
}
;==================================================
JEE_StrCount(ByRef vText, vNeedle, vCaseSen=0)
{
if (vNeedle = "")
return ""
vSCS := A_StringCaseSense
StringCaseSense, % vCaseSen ? "On" : "Off"
StrReplace(vText, vNeedle, "", vCount) ;seemed to be faster than line below
;StrReplace(vText, vNeedle, vNeedle, vCount)
StringCaseSense, % vSCS
return vCount
}
;==================================================
JEE_SortStable(vTextA, vTextB, vOffset) ;for use with AHK's Sort command
{
vRet := (vTextA "") > (vTextB) ? 1 : (vTextA "") < (vTextB) ? -1 : -vOffset
return vRet
}
;==================================================
;e.g. with vNeedle = countdown (equivalent to 'cdnnootuw')
;any words containing 2 of c/d/t/u/w are removed (e.g. RegEx needle: '`nm)^.*c.*c.*`n')
;or containing 3 of n/o are removed (e.g. RegEx needle: '`nm)^.*n.*n.*n.*`n')
;also vListRep is checked so that any words
;containing any letter not in 'cdnnootuw' are removed
;vList is an LF-delimited list
JEE_StrGetSubwords(vNeedle, vList, vOpt="", vRange1="", vRange2="", vListRep="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
{
vCaseSen := !!InStr(vOpt, "cs")
vPfx := vCaseSen ? "" : "i"
vSCS := A_StringCaseSense
StringCaseSense, % vCaseSen ? "On" : "Off"
if !(SubStr(vList, StrLen(vList)) = "`n")
vList .= "`n"
while !(vListRep = "")
{
vChar := SubStr(vListRep, 1, 1)
vListRep := RegExReplace(vListRep, vPfx ")\Q" vChar "\E", "")
if InStr(vNeedle, vChar, vCaseSen)
continue
vList := RegExReplace(vList, vPfx "`nm)^.*\Q" vChar "\E.*`n", "")
}
while !(vNeedle = "")
{
vChar := SubStr(vNeedle, 1, 1)
vNeedle2 := RegExReplace(vNeedle, vPfx ")[^" vChar "]*", ".*") vChar ".*"
vNeedle2 := StrReplace(vNeedle2, ".*.*", ".*")
vNeedle := StrReplace(vNeedle, vChar, "")
vList := RegExReplace(vList, vPfx "`nm)^" vNeedle2 "`n", "")
}
StringCaseSense, % vSCS
if (vRange1 vRange2 = "")
return SubStr(vList, 1, -1)
vOutput := ""
VarSetCapacity(vOutput, StrLen(vList2)*2)
vList := SubStr(vList, 1, -1)
Loop, Parse, vList, `n
if ((vRange1 = "") || (StrLen(A_LoopField) >= vRange1))
&& ((vRange2 = "") || (StrLen(A_LoopField) <= vRange2))
vList2 .= A_LoopField "`n"
return SubStr(vList2, 1, -1)
}
;==================================================
;e.g. ;vOrig: 'A,B,C', ;vList: 'a,b,c'
;output: 'Aa,Ab,Ac,Ba,Bb,Bc,Ca,Cb,Cc'
JEE_ListItemsPrepend(vOrig, vList, vSep=",")
{
StrReplace(vList, vSep, "", vCount), vCount += 1
vList := vSep vList
VarSetCapacity(vList2, (StrLen(vList)+vCount)*StrLen(vOrig)*2)
Loop, Parse, vOrig, % vSep
vList2 .= StrReplace(vList, vSep, vSep A_LoopField)
return SubStr(vList2, 2)
}
;==================================================
;e.g. 'qwe,rty,uio,pas,dfg,hjk,lzx,cvb,nm'
;output: 'eqw,rty,iou,aps,dfg,hjk,lxz,bcv,mn'
;vOpt: space-separated list: cs (case sensitive), st (stable)
JEE_ListItemsAlphabetise(vText, vDelim="", vOpt="")
{
vSCS := A_StringCaseSense
StringCaseSense, % InStr(vOpt, "cs") ? "On" : "Off"
;note: $ has issues as a backreference char in RegEx
(vDelim2 = "$") ? (vDelim2 := "$$") : (vDelim2 := vDelim)
vOpt2 := "D" vDelim (InStr(vOpt, "cs") ? " C" : "") (InStr(vOpt, "st") ? " F JEE_SortStable" : "")
vOutput := ""
VarSetCapacity(vOutput, (StrLen(vText)+1)*2)
Loop, Parse, vText, % vDelim
{
vTemp := RegExReplace(A_LoopField, "", vDelim2)
Sort, vTemp, % vOpt2
vOutput .= StrReplace(vTemp, vDelim) vDelim
}
StringCaseSense, % vSCS
return SubStr(vOutput, 1, -1)
}
;==================================================
JEE_StrAlphabetise(vText, vUnused="", vOpt="")
{
if (vUnused = "")
Loop, 300
{
if !InStr(vText, Chr(A_Index), 0)
{
vUnused := Chr(A_Index)
break
}
}
if (vUnused = "") || InStr(vText, vUnused)
{
MsgBox, % "warning: " A_ThisFunc ": no suitable delimiter found"
return vText
}
;note: for vUnused, '$' works here, '$$' is not needed (re. backreferences)
vText := RegExReplace(vText, "", vUnused)
if !InStr(vOpt, "st") ;sort unstable
Sort, vText, D%vUnused%
else ;sort stable
Sort, vText, D%vUnused% F JEE_SortStable
vText := StrReplace(vText, vUnused)
return vText
}
Last edited by jeeswg on 14 Jul 2017, 18:58, edited 3 times in total.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Here's a simple example explaining the main principles used:
- [get PR] to generate permutations with repetition: prepend letters to items in a list (explained lower down)
- [PR to P] to go from permutations with repetition to permutations (without repetition): use RegExReplace to remove any items that contain a letter more than once
- [PR to CR] to go from permutations with repetition to combinations with repetition: alphabetise each item, and remove duplicates
- [P to C] to go from permutations (without repetition) to combinations (without repetition): alphabetise each item, and remove duplicates
The trick to generate permutations with repetition:
a,b,c -> ,a,b,c
,a,b,c -> ,aa,ab,ac [replace ',' with ',a']
,a,b,c -> ,ba,bb,bc [replace ',' with ',b']
,a,b,c -> ,ca,cb,cc [replace ',' with ',c']
concatenate (and trim) to give: aa,ab,ac,ba,bb,bc,ca,cb,cc
- [get PR] to generate permutations with repetition: prepend letters to items in a list (explained lower down)
- [PR to P] to go from permutations with repetition to permutations (without repetition): use RegExReplace to remove any items that contain a letter more than once
- [PR to CR] to go from permutations with repetition to combinations with repetition: alphabetise each item, and remove duplicates
- [P to C] to go from permutations (without repetition) to combinations (without repetition): alphabetise each item, and remove duplicates
The trick to generate permutations with repetition:
a,b,c -> ,a,b,c
,a,b,c -> ,aa,ab,ac [replace ',' with ',a']
,a,b,c -> ,ba,bb,bc [replace ',' with ',b']
,a,b,c -> ,ca,cb,cc [replace ',' with ',c']
concatenate (and trim) to give: aa,ab,ac,ba,bb,bc,ca,cb,cc
Code: Select all
q:: ;combinations/permutations with/without repetition
vOrig := "a,b,c", vSep := ","
;vOrig := "a,b,c,d,e", vSep := ","
StrReplace(vOrig, ",", "", vCountOrig), vCountOrig += 1
;note: in this example there is no significance to the use of the StrSplit function,
;I am not using arrays, it is simply used as a hack to count the occurrences
;of a needle string within a haystack string, seeing as AHK doesn't have a StrCount function
;permutations with repetition
vList := vOrig
Loop, % vCountOrig - 1
{
MsgBox, % StrSplit(vList,",").Length() "`r`n" vList
StrReplace(vList, vSep, "", vCount), vCount += 1
vList := vSep vList
VarSetCapacity(vList2, (StrLen(vList)+vCount)*StrLen(vOrig)*2)
Loop, Parse, vOrig, % vSep
vList2 .= StrReplace(vList, vSep, vSep A_LoopField)
vList := SubStr(vList2, 2)
}
MsgBox, % "permutations with repetition: " StrSplit(vList,",").Length() "`r`n" vList
vListPR := vList
;permutations (without repetition)
;here, rather than filtering the 'permutations with repetitions' list,
;we are generating items, and filtering items, on the fly
vList := vOrig
Loop, % vCountOrig - 1
{
MsgBox, % StrSplit(vList,",").Length() "`r`n" vList
StrReplace(vList, vSep, "", vCount), vCount += 1
vList := vSep vList
VarSetCapacity(vList2, (StrLen(vList)+vCount)*StrLen(vOrig)*2)
Loop, Parse, vOrig, % vSep
vList2 .= StrReplace(vList, vSep, vSep A_LoopField)
vList := SubStr(vList2, 2)
;remove items that contain a letter more than once
vList := StrReplace(vList, ",", "`n") "`n"
;e.g. vList := RegExReplace(vList, "`nm)^.*a.*a.*`n", "")
Loop, Parse, vOrig, % ","
vList := RegExReplace(vList, "`nm)^.*" A_LoopField ".*" A_LoopField ".*`n", "")
vList := SubStr(vList, 1, -1)
vList := StrReplace(vList, "`n", ",")
}
MsgBox, % "permutations (without repetition): " StrSplit(vList,",").Length() "`r`n" vList
vListP := vList
;combinations with repetition
vListCR := ""
VarSetCapacity(vListCR, (StrLen(vListPR)+1)*2)
Loop, Parse, vListPR, % ","
{
vTemp := RegExReplace(A_LoopField, "", ",")
Sort, vTemp, D,
vListCR .= StrReplace(vTemp, ",") ","
}
vListCR := SubStr(vListCR, 1, -1)
Sort, vListCR, D, U
MsgBox, % "combinations with repetition: " StrSplit(vListCR,",").Length() "`r`n" vListCR
;combinations (without repetition)
vListC := ""
VarSetCapacity(vListC, (StrLen(vListP)+1)*2)
Loop, Parse, vListP, % ","
{
vTemp := RegExReplace(A_LoopField, "", ",")
Sort, vTemp, D,
vListC .= StrReplace(vTemp, ",") ","
}
vListC := SubStr(vListC, 1, -1)
Sort, vListC, D, U
MsgBox, % "combinations (without repetition): " StrSplit(vListC,",").Length() "`r`n" vListC
return
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Some anagram scripts, see above for the functions: JEE_StrGetSubwords and JEE_StrAlphabetise.
Code: Select all
;see basic example, that doesn't use the function, here:
;Anagrams - AutoHotkey Community
;https://autohotkey.com/boards/viewtopic.php?f=19&t=34240&p=158484#p158484
;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion.
;https://github.com/dwyl/english-words
q:: ;check for words that can be made from 'countdown'
;note: list is all lowercase letters excepts except for 2 hyphens
vPath = %A_Desktop%\words_alpha [dwyl english-words].txt
FileRead, vText, % vPath
vText := JEE_StrGetSubwords("countdown", vText)
vText := StrReplace(vText, "`n", "`r`n")
Clipboard := vText
MsgBox, % "done"
return
;==================================================
;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion.
;https://github.com/dwyl/english-words
w:: ;collect anagrams in a list
;note: list is all lowercase letters excepts except for 2 hyphens
vPath = %A_Desktop%\words_alpha [dwyl english-words].txt
FileRead, vText, % vPath
vOutput := ""
VarSetCapacity(vOutput, StrLen(vText)*3*2)
Loop, Parse, vText, `n, `r
vOutput .= JEE_StrAlphabetise(A_LoopField) "|" A_LoopField ","
vOutput := SubStr(vOutput,1,-1)
;the items are sorted because it's quicker to add keys to an array, in alphabetical order
Sort, vOutput, D,
StrReplace(vOutput, "," , "", vCount), vCount += 1
oArray := {}
oArray.SetCapacity(vCount)
Loop, Parse, vOutput, % ","
{
vPos := InStr(A_LoopField, "|")
vKey := SubStr(A_LoopField, 1, vPos-1)
vValue := SubStr(A_LoopField, vPos+1)
if (oArray[vKey] = "")
oArray[vKey] := vValue
else
oArray[vKey] := oArray[vKey] "," vValue
}
vOutput2 := ""
VarSetCapacity(vOutput2, StrLen(vOutput)*2)
for vKey, vValue in oArray
vOutput2 .= vKey "`t" vValue "`r`n"
Clipboard := vOutput2
;MsgBox, % oArray["aelrst"]
MsgBox, % oArray[JEE_StrAlphabetise("alters")]
oArray := ""
MsgBox, % "done"
return
Last edited by jeeswg on 18 Jul 2017, 11:44, edited 1 time in total.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
- littlegandhi1199
- Posts: 195
- Joined: 29 Aug 2016, 23:58
Re: combinations and permutations (and anagrams)
Here's a factorial function I've tested accurately up to 15jeeswg wrote:Some anagram scripts, see above for the functions: JEE_StrGetSubwords and JEE_StrAlphabetise.
Code: Select all
;see basic example, that doesn't use the function, here: ;Anagrams - AutoHotkey Community ;https://autohotkey.com/boards/viewtopic.php?f=19&t=34240&p=158484#p158484 ;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion. ;https://github.com/dwyl/english-words q:: ;check for words that can be made from 'countdown' ;note: list is all lowercase letters excepts except for 2 hyphens vPath = %A_Desktop%\words_alpha [dwyl english-words].txt FileRead, vText, % vPath vText := JEE_StrGetSubwords("countdown", vText) vText := StrReplace(vText, "`n", "`r`n") Clipboard := vText MsgBox, % "done" return ;================================================== ;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion. ;https://github.com/dwyl/english-words w:: ;collect anagrams in a list ;note: list is all lowercase letters excepts except for 2 hyphens vPath = %A_Desktop%\words_alpha [dwyl english-words].txt FileRead, vText, % vPath vOutput := "" VarSetCapacity(vOutput, StrLen(vText)*3*2) Loop, Parse, vText, `n, `r vOutput .= JEE_StrAlphabetise(A_LoopField) "|" A_LoopField "," vOutput := SubStr(vOutput,1,-1) ;the items are sorted because it's quicker to add keys to an array, in alphabetical order Sort, vOutput, D, StrReplace(vOutput, "," , "", vCount), vCount += 1 oArray := {} oArray.SetCapacity(vCount) Loop, Parse, vOutput, % "," { vPos := InStr(A_LoopField, "|") vKey := SubStr(A_LoopField, 1, vPos-1) vValue := SubStr(A_LoopField, vPos+1) if (oArray[vKey] = "") oArray[vKey] := vValue else oArray[vKey] := oArray[vKey] "," vValue } vOutput2 := "" VarSetCapacity(vOutput2, StrLen(vOutput)*2) for vKey, vValue in oArray vOutput2 .= vKey "`t" vValue "`r`n" Clipboard := vOutput2 MsgBox, % oArray["aelrst"] oArray := "" MsgBox, % "done" return
Factorial(n)
{
if n < 3
return n
else
return n*Factorial(n-1)
}
Script Backups on every Execution
https://www.autohotkey.com/boards/viewtopic.php?f=6&t=75767&p=328155#p328155
Scrabble Solver 4-15 letter word outputs ( # of inputs)
https://www.autohotkey.com/boards/viewtopic.php?f=19&t=34285
https://www.autohotkey.com/boards/viewtopic.php?f=6&t=75767&p=328155#p328155
Scrabble Solver 4-15 letter word outputs ( # of inputs)
https://www.autohotkey.com/boards/viewtopic.php?f=19&t=34285
Re: combinations and permutations (and anagrams)
Code: Select all
;AHK range: -0x8000000000000000 to 0x7FFFFFFFFFFFFFFF
;AHK range: -9223372036854775808 to 9223372036854775807
;20! = 2432902008176640000 ;within range
;limit = 9223372036854775807
;21! = 51090942171709440000 ;too big
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
My favorite Permutation function to date is Lexicographical next permutation in O(1) time.
Re: combinations and permutations (and anagrams)
I just realised, in this case, this applies,wolf_II wrote: This also keep them as integers, rather than floats.
Eg,Expressions wrote: When /= is the leftmost operator in an expression and it is not part of a multi-statement expression, it performs floor division unless one of the inputs is floating point
Code: Select all
a:=5
b:=2
c:=a/b
a/=b
Msgbox, % a "`n" c
Edit: To really avoid floats, we can work with rational numbers, primitive example, very briefly tested,
Code: Select all
msgbox % nchoosek(200,10) ; To big number for 32 bit.
nchoosek(n,k){
i:=1
r:=new rational(1,1)
Loop % k {
r.p*=n+1-A_Index
r.q*=A_Index
r.reduce()
}
return r.p
}
class rational {
; Primitive rational number, r=p/q ∈ ℚ, p,q ∈ ℝ, q != 0
__new(p,q){
this.p:=p
this.q:=q
}
add(p,q){
this.p+=p
this.q+=q
}
mul(p,q){
this.p*=p
this.q*=q
}
reduce(){
local p, q
p:=this.p
q:=this.q
rational._reduce(p,q)
this.p:=p
this.q:=q
}
print(){
return this.p . (this.q>1 && this.p!=0 ? "/" . this.q : "")
}
; Internal methods
_reduce(byref num, byref den){
/*
typedef struct rational {
long long int num;
long long int den;
} *rat;
*/
static type:= A_PtrSize == 4 ? "Int" : "Int64"
VarSetCapacity(rat,2*A_PtrSize)
NumPut(num,rat,0, type)
NumPut(den,rat,A_PtrSize, type)
DllCall(rational.pred, "ptr", &rat, "ptr", rational.pabs, "ptr", rational.pgcd, "Cdecl")
num:=numget(&rat,0, type)
den:=numget(&rat,A_PtrSize, type)
}
; Binary code:
; For 32 bit, all long long int are long int.
cAbs(){
/* c source:
long long int abs(long long int x){
return x < 0 ? -x : x;
}
*/
local k, i, raw, bin
static flProtect:=0x40, flAllocationType:=0x1000 ; PAGE_EXECUTE_READWRITE ; MEM_COMMIT
static raw32:=[69485707,701510041,2425406416,2425393296]
static raw64:=[1221232968,3242772617,826818554,3492366544,2425393347,2425393296,2425393296,2425393296]
bin:=DllCall("Kernel32.dll\VirtualAlloc", "Uptr",0, "Ptr", (raw:=A_PtrSize==4?raw32:raw64).length()*4, "Uint", flAllocationType, "Uint", flProtect, "Ptr")
for k, i in raw
NumPut(i,bin+(k-1)*4,"Int")
return bin
}
cGcd(){
/* c source:
typedef long long int (*pabs)(long long int);
long long int gcd(long long int a, long long int b, pabs abs){
a=abs(a);
b=abs(b);
int rem;
if (a < b) {
int tmp;
tmp = a;
a = b;
b = tmp;
}
rem = a % b;
while (rem != 0) {
a = b;
b = rem;
rem = a % b;
}
return b;
}
*/
local k, i, raw, bin
static flProtect:=0x40, flAllocationType:=0x1000 ; PAGE_EXECUTE_READWRITE ; MEM_COMMIT
static raw32:=[3968029526,608471828,611617568,604277032,3280590591,606356619,4280550537,2311272918,2298904001,2311817688,2581105089,3531995639,242602889,1988960235,666668288,0,3364475785,4154055049,1976731131,348423155,1583077513,3955984835,2425393396,2425393296]
static raw64:=[1213421143,1210117251,2303514505,3506389446,1220774216,3607099785,1220753736,159236489,1220764488,2303249289,3632875713,4148730184,1104315897,678744457,8658703,0,1304987976,2571682147,1237420364,3531995383,1976666433,3230223595,549749576,3277807195,3955788105,2425393392,2425393296,2425393296]
bin:=DllCall("Kernel32.dll\VirtualAlloc", "Uptr",0, "Ptr", (raw:=A_PtrSize==4?raw32:raw64).length()*4, "Uint", flAllocationType, "Uint", flProtect, "Ptr")
for k, i in raw
NumPut(i,bin+(k-1)*4,"Int")
return bin
}
cRed(){
/* c source:
typedef long long int (*pabs)(long long int);
typedef long long int (*pgcd)(long long int,long long int,pabs);
typedef struct rational {
long long int num;
long long int den;
} *rat;
void reduce(rat x, pabs abs, pgcd gcd){
if (x->num==0){
x->den=1;
return;
}
if (abs(x->num)==1)
return;
if (x->num==x->den){
x->num=1;
x->den=1;
return;
}
int maxdiv=gcd(x->num,x->den,abs);
x->num/=maxdiv;
x->den/=maxdiv;
return;
}
*/
local k, i, raw, bin
static flProtect:=0x40, flAllocationType:=0x1000 ; PAGE_EXECUTE_READWRITE ; MEM_COMMIT
static raw32:=[418153299,539253899,3229942667,1137119861,260,415531776,3062743899,0,4280550537,2200183892,3916694008,1401619339,1959803140,608996139,609519908,604276996,136596617,673469695,59490697,2314860441,71535363,2314860441,3296920643,2428721944,66503,2800418816,2425393296,2425393296]
static raw64:=[1213421143,1210117251,2336803721,3599321097,1221036364,410372485,138659656,1,549749576,3277807195,8658703,0,2202587903,3899916792,1208716104,1208505227,745853241,4293953865,3361949911,1208191816,4193732761,1208191304,1208501131,4193732761,138643784,549749576,3277807195,4202255,17024840,3942645760,2425393311,2425393296]
bin:=DllCall("Kernel32.dll\VirtualAlloc", "Uptr",0, "Ptr", (raw:=A_PtrSize==4?raw32:raw64).length()*4, "Uint", flAllocationType, "Uint", flProtect, "Ptr")
for k, i in raw
NumPut(i,bin+(k-1)*4,"Int")
return bin
}
static pabs:=rational.cAbs()
static pgcd:=rational.cGcd()
static pred:=rational.cRed()
}
Re: combinations and permutations (and anagrams)
A script for doing word searches:
E.g. 'cou?????n' gives 'countdown' and 'courtesan'.
@Sam_: Cheers for the link.
E.g. 'cou?????n' gives 'countdown' and 'courtesan'.
Code: Select all
;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion.
;https://github.com/dwyl/english-words
q:: ;word search - Excel-style wildcards e.g. ? for 1 char, * for 0+ chars
vPath = %A_Desktop%\words_alpha [dwyl english-words].txt
FileRead, vText, % vPath
vText := StrReplace(vText, "`r`n", "`n") "`n"
vDefault := "co??????n"
InputBox, vNeedle,, "specify wildcard needle:",,,,,,,, % vDefault
;deal with special characters: \.*?+[{|()^$
vNeedle := RegExReplace(vNeedle, "[\Q\.+[{|()^$\E]", "\$0")
vNeedle := StrReplace(vNeedle, "?", ".")
vNeedle := StrReplace(vNeedle, "*", ".*")
vText := RegExReplace(vText, "`nm)(^" vNeedle "`n)|^.*`n", "$1")
vText := StrReplace(vText, "`n", "`r`n")
Clipboard := vText
MsgBox, % "done"
return
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Anagrams: a script to split words into two words e.g.:
[AutoHotkey]
AeHtu kooty|haute|kyoto,tokyo
Aekot Hotuy|atoke|youth
Aekottu Hoy|outtake,takeout|hoy
AHooty ektu|hootay|ketu,teuk,tuke
Akttu eHooy|kutta|hooey,hooye
Aootty eHku|toyota|heuk,huke,kueh
Aottu eHkoy|tatou|hokey
Aotu eHkoty|auto|hotkey
Attu eHkooy|tatu,taut|hookey
[AutoHotkey]
AeHtu kooty|haute|kyoto,tokyo
Aekot Hotuy|atoke|youth
Aekottu Hoy|outtake,takeout|hoy
AHooty ektu|hootay|ketu,teuk,tuke
Akttu eHooy|kutta|hooey,hooye
Aootty eHku|toyota|heuk,huke,kueh
Aottu eHkoy|tatou|hokey
Aotu eHkoty|auto|hotkey
Attu eHkooy|tatu,taut|hookey
Code: Select all
;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion.
;https://github.com/dwyl/english-words
q:: ;anagrams - split words into two words
;collect anagrams in a list
;note: list is all lowercase letters excepts except for 2 hyphens
vPath = %A_Desktop%\words_alpha [dwyl english-words].txt
FileRead, vText, % vPath
vOutput := ""
VarSetCapacity(vOutput, StrLen(vText)*3*2)
Loop, Parse, vText, `n, `r
vOutput .= JEE_StrAlphabetise(A_LoopField) "|" A_LoopField ","
vOutput := SubStr(vOutput,1,-1)
;the items are sorted because it's quicker to add keys to an array, in alphabetical order
Sort, vOutput, D,
StrReplace(vOutput, "," , "", vCount), vCount += 1
oArray := {}
oArray.SetCapacity(vCount)
Loop, Parse, vOutput, % ","
{
vPos := InStr(A_LoopField, "|")
vKey := SubStr(A_LoopField, 1, vPos-1)
vValue := SubStr(A_LoopField, vPos+1)
if (oArray[vKey] = "")
oArray[vKey] := vValue
else
oArray[vKey] := oArray[vKey] "," vValue
}
MsgBox, % oArray[JEE_StrAlphabetise("one")]
MsgBox, % oArray[JEE_StrAlphabetise("two")]
MsgBox, % oArray[JEE_StrAlphabetise("eleven")]
MsgBox, % oArray[JEE_StrAlphabetise("twelve")]
vListNeedles := "eleven two,twelve one,AutoHotkey"
vOutput := ""
Loop, Parse, vListNeedles, % ","
{
vNeedleOrig := A_LoopField
vNeedle := StrReplace(vNeedleOrig, " ")
vLen := StrLen(vNeedle)
vOutputTemp := ""
oTemp := {}
Loop, % 2**vLen
{
vTemp1 := vTemp2 := ""
vBin := JEE_Dec2Bin(A_Index-1, vLen)
Loop, Parse, vBin
if A_LoopField
vTemp1 .= SubStr(vNeedle, A_Index, 1)
else
vTemp2 .= SubStr(vNeedle, A_Index, 1)
vTemp1 := JEE_StrAlphabetise(vTemp1)
vTemp2 := JEE_StrAlphabetise(vTemp2)
if !oArray.HasKey(vTemp1) || !oArray.HasKey(vTemp2)
continue
if (vTemp1 > vTemp2)
continue
if oTemp.HasKey(vTemp1 " " vTemp2)
continue
oTemp[vTemp1 " " vTemp2] := ""
vOutputTemp .= vTemp1 " " vTemp2 "|" oArray[vTemp1] "|" oArray[vTemp2] "`n"
}
Sort, vOutputTemp, U
vOutputTemp := StrReplace(vOutputTemp, "`n", "`r`n")
vOutput .= "[" vNeedleOrig "]`r`n" vOutputTemp "`r`n"
}
oArray := ""
Clipboard := SubStr(vOutput, 1, -2)
MsgBox, % vOutput
return
;==================================================
JEE_StrAlphabetise(vText, vUnused="", vOpt="")
{
if (vUnused = "")
Loop, 300
{
if !InStr(vText, Chr(A_Index), 0)
{
vUnused := Chr(A_Index)
break
}
}
if (vUnused = "") || InStr(vText, vUnused)
{
MsgBox, % "warning: " A_ThisFunc ": no suitable delimiter found"
return vText
}
;note: for vUnused, '$' works here, '$$' is not needed (re. backreferences)
vText := RegExReplace(vText, "", vUnused)
if !InStr(vOpt, "st") ;sort unstable
Sort, vText, D%vUnused%
else ;sort stable
Sort, vText, D%vUnused% F JEE_SortStable
vText := StrReplace(vText, vUnused)
return vText
}
;==================================================
;where vLen is the minimum length of the number to return (i.e. pad it with zeros if necessary)
JEE_Dec2Bin(vNum, vLen=1)
{
if (SubStr(vNum, 1, 2) = "0x")
vNum += 0
if !RegExMatch(vNum, "^\d+$")
return ""
while vNum
vBin := (vNum & 1) vBin, vNum >>= 1
return Format("{:0" vLen "}", vBin)
;if (StrLen(vBin) < vLen)
; Loop, % vLen - StrLen(vBin)
; vBin := "0" vBin
;return vBin
}
;==================================================
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Just a few links from rosettacode (maybe its useful)
Anagrams
Permutations
Combinations and permutations
...
Anagrams
Permutations
Combinations and permutations
...
[AHK] v2.0.5 | [WIN] 11 Pro (Version 22H2) | [GitHub] Profile
Re: combinations and permutations (and anagrams)
Anagrams: a script to split words into multiple words e.g.:
[AutoHotkey][note: selected results, many results removed]
Aekt Hot ouy|kate,keat,keta,take,teak|hot,tho|you
AHot eky otu|oath|key,kye|out,tou
AHt ekoy otu|aht,hat,tha|okey,yoke|out,tou
AHtu eky oot|auth,haut,utah|key,kye|oot,oto,too
Ako eHty otu|ako,koa,oak,oka|hyte,they,yeth|out,tou
Ako eHy ottu|ako,koa,oak,oka|hey,hye,yeh|tout
Ako ety Hotu|ako,koa,oak,oka|ety,tye,yet|hout,thou
Aot ekoy Htu|oat,tao,toa|okey,yoke|hut
Aot eky Hotu|oat,tao,toa|key,kye|hout,thou
***Aotu eky Hot|auto|key,kye|hot,tho***
Attu eky Hoo|tatu,taut|key,kye|hoo,oho,ooh
@jNizM: Many thanks. I already had so many scripts to look through!
[AutoHotkey][note: selected results, many results removed]
Aekt Hot ouy|kate,keat,keta,take,teak|hot,tho|you
AHot eky otu|oath|key,kye|out,tou
AHt ekoy otu|aht,hat,tha|okey,yoke|out,tou
AHtu eky oot|auth,haut,utah|key,kye|oot,oto,too
Ako eHty otu|ako,koa,oak,oka|hyte,they,yeth|out,tou
Ako eHy ottu|ako,koa,oak,oka|hey,hye,yeh|tout
Ako ety Hotu|ako,koa,oak,oka|ety,tye,yet|hout,thou
Aot ekoy Htu|oat,tao,toa|okey,yoke|hut
Aot eky Hotu|oat,tao,toa|key,kye|hout,thou
***Aotu eky Hot|auto|key,kye|hot,tho***
Attu eky Hoo|tatu,taut|key,kye|hoo,oho,ooh
Code: Select all
;GitHub - dwyl/english-words: A text file containing 479k English words for fast search auto-completion / autosuggestion.
;https://github.com/dwyl/english-words
q:: ;anagrams - split words into multiple words
;collect anagrams in a list
;note: list is all lowercase letters excepts except for 2 hyphens
vPath = %A_Desktop%\words_alpha [dwyl english-words].txt
FileRead, vText, % vPath
vOutput := ""
VarSetCapacity(vOutput, StrLen(vText)*3*2)
Loop, Parse, vText, `n, `r
vOutput .= JEE_StrAlphabetise(A_LoopField) "|" A_LoopField ","
vOutput := SubStr(vOutput,1,-1)
;the items are sorted because it's quicker to add keys to an array, in alphabetical order
Sort, vOutput, D,
StrReplace(vOutput, "," , "", vCount), vCount += 1
oArray := {}
oArray.SetCapacity(vCount)
Loop, Parse, vOutput, % ","
{
vPos := InStr(A_LoopField, "|")
vKey := SubStr(A_LoopField, 1, vPos-1)
vValue := SubStr(A_LoopField, vPos+1)
if (oArray[vKey] = "")
oArray[vKey] := vValue
else
oArray[vKey] := oArray[vKey] "," vValue
}
MsgBox, % oArray[JEE_StrAlphabetise("one")]
MsgBox, % oArray[JEE_StrAlphabetise("two")]
MsgBox, % oArray[JEE_StrAlphabetise("eleven")]
MsgBox, % oArray[JEE_StrAlphabetise("twelve")]
vListNeedles := "eleven two,twelve one,AutoHotkey,together"
vOutput := ""
vCountSplit := 3 ;number of words to split word/phrase into
vRange1 := 3 ;minimum number of characters per split
vRange2Orig := "" ;maximum number of characters per split
oTemp := {}
Loop, Parse, vListNeedles, % ","
{
vNeedleOrig := A_LoopField
vNeedle := StrReplace(vNeedleOrig, " ")
vLen := StrLen(vNeedle)
vOutputTemp := ""
oArray2 := {}
if (vRange2Orig = "")
vRange2 := vLen-vCountSplit+1
else
vRange2Orig := vRange2Orig
Loop, % vCountSplit**vLen
{
vBase := JEE_Dec2BaseCSL(A_Index-1, vCountSplit, vLen)
Loop, % vCountSplit
oTemp[A_Index] := ""
Loop, Parse, vBase, % ","
oTemp[A_LoopField+1] .= SubStr(vNeedle, A_Index, 1)
vTemp := "", vListTemp := ""
vDoContinue := 0
Loop, % vCountSplit
{
if (StrLen(oTemp[A_Index]) < vRange1)
|| (StrLen(oTemp[A_Index]) > vRange2)
{
vDoContinue := 1
break
}
vTemp := JEE_StrAlphabetise(oTemp[A_Index])
if !oArray.HasKey(vTemp)
{
vDoContinue := 1
break
}
vListTemp .= (A_Index=1?"":" ") vTemp
}
if vDoContinue
continue
Sort, vListTemp, D%A_Space%
if oArray2.HasKey(vListTemp)
continue
oArray2[vListTemp] := ""
vOutputTemp .= vListTemp
Loop, Parse, vListTemp, % " "
vOutputTemp .= "|" oArray[A_LoopField]
vOutputTemp .= "`n"
}
Sort, vOutputTemp, U
vOutputTemp := StrReplace(vOutputTemp, "`n", "`r`n")
vOutput .= "[" vNeedleOrig "]`r`n" vOutputTemp "`r`n"
}
oArray := ""
Clipboard := SubStr(vOutput, 1, -2)
MsgBox, % vOutput
return
;==================================================
;handles non-negative integers
;creates a comma-separated list of decimal numbers
JEE_Dec2BaseCSL(vNum, vBase, vLen=1)
{
if (SubStr(vNum, 1, 2) = "0x")
vNum += 0
if !RegExMatch(vNum, "^\d+$")
return ""
if (vNum = 0)
{
Loop, % vLen
vOutput .= "0,"
return SubStr(vOutput, 1, -1)
}
while vNum
vOutput := Mod(vNum, vBase) "," vOutput, vNum //= vBase
StrReplace(vOutput, ",", "", vCount)
if (vCount < vLen)
Loop, % vLen - vCount
vOutput := "0," vOutput
return SubStr(vOutput, 1, -1)
}
;==================================================
JEE_StrAlphabetise(vText, vUnused="", vOpt="")
{
if (vUnused = "")
Loop, 300
{
if !InStr(vText, Chr(A_Index), 0)
{
vUnused := Chr(A_Index)
break
}
}
if (vUnused = "") || InStr(vText, vUnused)
{
MsgBox, % "warning: " A_ThisFunc ": no suitable delimiter found"
return vText
}
;note: for vUnused, '$' works here, '$$' is not needed (re. backreferences)
vText := RegExReplace(vText, "", vUnused)
if !InStr(vOpt, "st") ;sort unstable
Sort, vText, D%vUnused%
else ;sort stable
Sort, vText, D%vUnused% F JEE_SortStable
vText := StrReplace(vText, vUnused)
return vText
}
;==================================================
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Permutations: a script to get the next permutation e.g. 'aaa' to 'aab', 'zzz' to 'aaaa'.
[EDIT:] I added a function to get the previous permutation.
Code: Select all
q:: ;string get next permutation
vText := "aaa"
Loop, 40
{
vOutput .= vText "`r`n"
vText := JEE_StrPermutNext(vText, "c")
}
vOutput .= "`r`n"
vText := "ccc"
Loop, 40
{
vOutput .= vText "`r`n"
vText := JEE_StrPermutNext(vText, "e", "c")
}
vOutput .= "`r`n"
vText := "0"
Loop, 40
{
vOutput .= vText "`r`n"
vText := JEE_StrPermutNext(vText, "1", "0")
}
vOutput .= "`r`n"
vText := "A"
Loop, 100
{
vOutput .= vText "`r`n"
vText := JEE_StrPermutNext(vText, "_", "A")
}
vOutput .= "`r`n"
Clipboard := SubStr(vOutput, 1, -2)
MsgBox, % "done"
return
;==================================================
;e.g. aaa -> aab, aab -> aac, zzy -> zzz, zzz -> aaaa
;vStartChar a, vEndChar z, for aaaa to zzzz
;vStartChar a, vEndChar d, for aaaa to dddd
;JEE_StrNextWord
;JEE_StrNextWordPermutation
JEE_StrPermutNext(vText, vEndChar:="z", vStartChar:="a")
{
vLen := StrLen(vText)
if (vLen = 0)
return vStartChar
else if (SubStr(vText, vLen) == vEndChar)
{
vText2 := ""
Loop, % vLen
if (SubStr(vText,vLen+1-A_Index,1) == vEndChar)
vCount := A_Index, vText2 .= vStartChar
else
break
if (vCount = vLen)
return vText2 vStartChar
else if (vCount+1 = vLen)
return Chr(Ord(SubStr(vText,1,1))+1) vText2
else
return SubStr(vText,1,vLen-vCount-1) Chr(Ord(SubStr(vText,vLen-vCount,1))+1) vText2
}
else
return SubStr(vText,1,vLen-1) Chr(Ord(SubStr(vText,vLen))+1)
}
;==================================================
JEE_StrPermutPrev(vText, vEndChar:="z", vStartChar:="a")
{
vLen := StrLen(vText)
if (vLen = 0)
return
else if (SubStr(vText, vLen) == vStartChar)
{
vText2 := ""
Loop, % vLen
if (SubStr(vText,vLen+1-A_Index,1) == vStartChar)
vCount := A_Index, vText2 .= vEndChar
else
break
if (vCount = vLen)
return SubStr(vText2, 1, -1)
else if (vCount+1 = vLen)
return Chr(Ord(SubStr(vText,1,1))-1) vText2
else
return SubStr(vText,1,vLen-vCount-1) Chr(Ord(SubStr(vText,vLen-vCount,1))-1) vText2
}
else
return SubStr(vText,1,vLen-1) Chr(Ord(SubStr(vText,vLen))-1)
}
Last edited by jeeswg on 07 Aug 2017, 07:18, edited 4 times in total.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Not sure if this is (somehow) useful. I did this for someone (cant remember) on irc.
Number to Letter from 1 (A) to (e.g.) 18278 (ZZZ)
Number to Letter from 1 (A) to (e.g.) 18278 (ZZZ)
Code: Select all
arr := []
loop % 18278
arr.Push(ConvertToLetter(A_Index))
; ===============================================================================================================================
Gui, Add, ListView, xm ym w400 h400, % "Number|Letter"
for i, v in arr
LV_Add("", i, arr[i])
Gui, Show, AutoSize
return
; ===============================================================================================================================
ConvertToLetter(n)
{
while (n != 0)
t := mod((n - 1), 26), n := (n - t) // 26, l := chr(65 + t) l
return l
}
; ===============================================================================================================================
GuiEscape:
GuiClose:
ExitApp
; ===============================================================================================================================
[AHK] v2.0.5 | [WIN] 11 Pro (Version 22H2) | [GitHub] Profile
Re: combinations and permutations (and anagrams)
@jNizM: Thanks, that's some very nice code for Excel column numbers to letters:
Excel column letters:
A-Z (1-26) [26^1 = 26]
AA-ZZ (27-702) [26^2 = 676]
AAA-ZZZ (703-18278) [26^3 = 17576]
I'm planning to release some code for Excel column letters <--> numbers in a future Excel tutorial.
==================================================
A script demonstrating jNizM's ConvertToLetter function, and confirming that it gives the same results as my JEE_StrPermutNext function.
Excel column letters:
A-Z (1-26) [26^1 = 26]
AA-ZZ (27-702) [26^2 = 676]
AAA-ZZZ (703-18278) [26^3 = 17576]
I'm planning to release some code for Excel column letters <--> numbers in a future Excel tutorial.
==================================================
A script demonstrating jNizM's ConvertToLetter function, and confirming that it gives the same results as my JEE_StrPermutNext function.
Code: Select all
q:: ;Excel - get next column letter(s)
vText := ""
Loop, 18278
{
vText := JEE_StrPermutNext(vText, "Z", "A")
vText2 := ConvertToLetter(A_Index)
;if !(vText = vText2)
MsgBox, % A_Index " " vText " " vText2
}
MsgBox, % "done"
return
;==================================================
ConvertToLetter(n)
{
while (n != 0)
t := mod((n - 1), 26), n := (n - t) // 26, l := chr(65 + t) l
return l
}
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Re: combinations and permutations (and anagrams)
Script for:
- permutations: get next 'word'/get nth 'word'/'word' to n
- Excel: get next column letter(s)/get nth column letter(s)/column letter(s) to n
Introducing functions:
- JEE_StrExcelColNumToLet
- JEE_StrExcelColLetToNum
- JEE_StrPermutNumToWord
- JEE_StrPermutWordToNum
- permutations: get next 'word'/get nth 'word'/'word' to n
- Excel: get next column letter(s)/get nth column letter(s)/column letter(s) to n
Introducing functions:
- JEE_StrExcelColNumToLet
- JEE_StrExcelColLetToNum
- JEE_StrPermutNumToWord
- JEE_StrPermutWordToNum
Code: Select all
;note: requires JEE_StrPermutNext from above
q:: ;permutations - get next 'word'/get nth 'word'/'word' to n
;Excel - get next column letter(s)/get nth column letter(s)/column letter(s) to n
vText := ""
vCount := 4
vOrd := Ord("a")
vOutput := ""
VarSetCapacity(vOutput, 1000000*2)
Loop, 18278
{
vText := JEE_StrPermutNext(vText, "Z", "A")
vText2 := JEE_StrExcelColNumToLet(A_Index)
vNum := JEE_StrExcelColLetToNum(vText)
;vText := JEE_StrPermutNext(vText, "d", "a")
;vText2 := JEE_StrPermutNumToWord(A_Index, vCount, vOrd)
;vNum := JEE_StrPermutWordToNum(vText, vCount, vOrd)
if !(vText = vText2) || !(A_Index = vNum)
MsgBox, % A_Index " " vText " " vText2 " " vNum
vOutput .= A_Index "`t" vText "`r`n"
}
Clipboard := vOutput
MsgBox, % "done"
return
;==================================================
JEE_StrExcelColNumToLet(vNum)
{
vLet := ""
while vNum
vLet := Chr(65+Mod(vNum-1,26)) vLet, vNum := (vNum-1)//26
return vLet
}
;==================================================
JEE_StrExcelColLetToNum(vLet)
{
vNum := 0
Loop, % vLen := StrLen(vLet)
vNum += (Ord(SubStr(vLet,vLen-A_Index+1,1))-64)*(26**(A_Index-1))
return vNum
}
;==================================================
JEE_StrPermutNumToWord(vNum, vCount:=26, vOrd:=97)
{
vLet := ""
while vNum
vLet := Chr(vOrd+Mod(vNum-1,vCount)) vLet, vNum := (vNum-1)//vCount
return vLet
}
;==================================================
JEE_StrPermutWordToNum(vLet, vCount:=26, vOrd:=97)
{
vNum := 0
Loop, % vLen := StrLen(vLet)
vNum += (Ord(SubStr(vLet,vLen-A_Index+1,1))-vOrd+1)*(vCount**(A_Index-1))
return vNum
}
;==================================================
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA