combinations and permutations (and anagrams)

Get help with using AutoHotkey (v1.1 and older) and its commands and hotkeys
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

combinations and permutations (and anagrams)

09 Jul 2017, 15:37

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
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
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: combinations and permutations

09 Jul 2017, 16:38

I have this one ready to post:

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
}
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
Last edited by wolf_II on 13 Jul 2017, 04:18, edited 2 times in total.
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations

09 Jul 2017, 19:01

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:

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
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: combinations and permutations

09 Jul 2017, 22:24

jeeswg 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.
I used in the past preccalc (32/64 bit versions available) from http://petr.lastovicka.sweb.cz/others.html#pi
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

11 Jul 2017, 16:21

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
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

11 Jul 2017, 16:38

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

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
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

14 Jul 2017, 15:51

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
User avatar
littlegandhi1199
Posts: 195
Joined: 29 Aug 2016, 23:58

Re: combinations and permutations (and anagrams)

14 Jul 2017, 18:39

jeeswg 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
Here's a factorial function I've tested accurately up to 15
Factorial(n)
{
if n < 3
return n
else
return n*Factorial(n-1)
}
Script Backups on every Execution :mrgreen:
https://www.autohotkey.com/boards/viewtopic.php?f=6&t=75767&p=328155#p328155

Scrabble Solver 4-15 letter word outputs ( :crazy: # of inputs)
https://www.autohotkey.com/boards/viewtopic.php?f=19&t=34285
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

14 Jul 2017, 18:57

Code: Select all

;AHK range: -0x8000000000000000 to 0x7FFFFFFFFFFFFFFF
;AHK range: -9223372036854775808 to 9223372036854775807

;20!   = 2432902008176640000 ;within range
;limit = 9223372036854775807
;21!   = 51090942171709440000 ;too big
I've now posted a JEE_Fact function above.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Helgef
Posts: 4709
Joined: 17 Jul 2016, 01:02
Contact:

Re: combinations and permutations (and anagrams)

15 Jul 2017, 11:49

wolf_II wrote: This also keep them as integers, rather than floats.
I just realised, in this case, this applies,
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
Eg,

Code: Select all

a:=5
b:=2
c:=a/b
a/=b
Msgbox, % a "`n" c
It is fixed in v2 :thumbup:

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()
}
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

15 Jul 2017, 13:46

A script for doing word searches:

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
@Sam_: Cheers for the link.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

18 Jul 2017, 12:44

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

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
User avatar
jNizM
Posts: 3183
Joined: 30 Sep 2013, 01:33
Contact:

Re: combinations and permutations (and anagrams)

19 Jul 2017, 00:59

Just a few links from rosettacode (maybe its useful)
Anagrams
Permutations
Combinations and permutations
...
[AHK] v2.0.5 | [WIN] 11 Pro (Version 22H2) | [GitHub] Profile
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

19 Jul 2017, 01:37

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

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
}

;==================================================
@jNizM: Many thanks. I already had so many scripts to look through!
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

07 Aug 2017, 05:40

Permutations: a script to get the next permutation e.g. 'aaa' to 'aab', 'zzz' to 'aaaa'.

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)
}
[EDIT:] I added a function to get the previous permutation.
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
User avatar
jNizM
Posts: 3183
Joined: 30 Sep 2013, 01:33
Contact:

Re: combinations and permutations (and anagrams)

07 Aug 2017, 05:57

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)

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
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

07 Aug 2017, 06:23

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

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
User avatar
jeeswg
Posts: 6902
Joined: 19 Dec 2016, 01:58
Location: UK

Re: combinations and permutations (and anagrams)

13 Aug 2017, 17:08

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

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

Return to “Ask for Help (v1)”

Who is online

Users browsing this forum: masheen, mikeyww and 161 guests