I love when that happensWhen I woke up, somehow I knew exactly
Cheers
I love when that happensWhen I woke up, somehow I knew exactly
Helgef wrote:Hello. I have several comments.
First,I still think this is true, however, trying to improve serves other purposes, such as learning and just having fun So I will try to contribute with some ideas.Helgef wrote:I see little need to improve something that works more or less instantly, in a on-user-typing context.
First some general comments. When we try to improve performance, we need to start where it matters. To know where that is, we have to benchmark, or measure what we can, and see where we actually spend our time. For example, I found that for input string
"abcdefghijklmno" the linetakes almost half a second however,Code: Select all
GuiControl,, LBox, % "|" (WordList ? WordList : "no anagrams for " String)
takes ~150 ms, simple improvment! Here are my measurments, for input string "abcdefghijklmnop", 16 letters,Code: Select all
GuiControl, hide, LBox GuiControl,, LBox, % "|" (WordList ? WordList : "no anagrams for " String) GuiControl, show, LBox
So combinations() is the culprit, no surprise really. The sort we needn't think about.Code: Select all
Calling combinations(): Elapsed time is: 4113.042499ms. KeyWord for-Loop: Elapsed time is: 385.292392ms. sort wordlist: Elapsed time is: 38.878966ms. Update Lbox: Elapsed time is: 575.462063ms.
The problem with combinations() as you noted, is the repetions, there are minor issues with the implementation, but really the problem is the algorthim. About the implementation, one thing that stands out is that you dobut then return NextShorter and then you doCode: Select all
Keyword := make_Keyword(NextShorter)
again, you could return the KeyWord instead, its not gonna save you but still it is a bit wasteful. Note, then you needCode: Select all
Keyword := make_Keyword(SubString)
for correct lookups. (I think )Code: Select all
AdjLength := StrLen(KeyWord) // 2 + 1
Regarding the algorithm, during the no-spoiler period, I did implement a general combination function,I try to explain in comments. It is general because it doesn't concatenate strings, it takes any collection of items and do all combinations, without repeats and organise the result in arrays. So this is not directly usable for your case, but could easily be adepted, I know because I have done it .Code: Select all
combine(items){ ; Combines all entries in the items array, without repetion. (Each entry is considered unique) ; Output is on the from all := [l1,...,ln], where lk is an ; array of all k-length combinations, ∀k ∈ [1,n], where n is the number of items of the input. ; Eg, ; items:=["a","b","c"] -> l1:=[ ["a"],["b"],["c"] ], l2:=[ [["a"],["b"]], [["a"],["c"]], [["b"],["c"]] ], l3:= [ ["a","b","c"] ] ; Total number of combinations are 2**n-1 (excluding the choise where nothing is choosen), each level, lk, in the out put hold nChoosek(n,k) combinations. /* About the algorithm: We build the combinations from level 1 and upwards to level n, that is In code we store an index along side each combination, denoted nI, of where to begin the choises on the next level. Choises are only made from the items array, the input. eg items[nI]. Each combination is allowed to choose from all items[k] ∀ k >= nI up to n (number of items) Eg, items:=[a,b,c], that is, item1 = a, item2 = b, item3 = c We initialise the first level: l1:= [ {1:a,nextInd:2}, {2:b,nextInd:3}, {3:c, nextInd:4} ] when we build the next level, that is l2, which is all combinations of length 2 we look at level 1, l1, and look at the first combination, which is comb1 := {1:a, nextInd:2} here we see that this combination starts its choises on index 2, (nI:=comb1.nextInd = 2), which is items[2] -> b newCombination1 := [1:a, 2:b, nextInd:nI+1 = 3] and increment the index counter. now nI+1=3 so one more choise, items[3]=c newCombination2 := [1:a, 2:c, nextInd:nI+2 = 4] and increment. nextInd>n, no more choises. Continue with combination 2 on level 1, comb2 := [2:b,nextInd:3], it starts its choises on index 3, that is nI=3, yields, newCombination3:= {1:a, 2:c, nextInd:nI+1 = 4}, nextInd>n, no more choises. For comb3 := {3:c, nextInd:4} we see that nextInd > n, no choise allowed. Level 2 is completed, start at building level 3. First look at comb1 in level 2, which is newCombination1 above, we see newCombination1:= {1:a, 2:b, nextInd:3} -> newComb:=[1:a, 2:b, 3:c, nextInd = 4], no more choise. Continuing we see all nextInd > n, we are done. Visualisation of the result: Level: 1 Level: 2 Level: 3 #1: a #1: ab #1: abc #2: b #2: ac #3: c #3: bc */ n:=items.length() ; Number of items all:=[] ; Result storage, output. all.setcapacity(n) ; level:=[] ; Level k, holds all combinations of lenght k. (i.e., the combining of k items) for k, item in items level.push({1:item,nextInd:k+1}) ; k=1 is first, lk:=[item1,...,itemn], an index is stored along side each item, for tracking purposes, it is removed when not needed. loop % n-1 { ; there are n levels all.push(level) ; Store level k, k=1 is compeleted on loop entry, next level is completed at bottom of loop nextLevel:=[] ; Create next level array nextLevel.SetCapacity(nchoosek(n,A_Index+1)) ; And set capacity, it holds nchoosek(n,k) items. for k, comb in level { ; go through all combinations in level k. nI:=comb.nextInd ; Get the combinations next index. comb.delete("nextInd") ; Delete it from the comb-array if (nI>n) ; if next index is greater than the number items, n, no choise is available, continue to next combination. continue loop % n-nI+1 { ; Combination is allowed to make choises newComb:=comb.clone() ; clone combination newComb.nextInd:=nI+A_Index ; Increment nextInd for the new combination newComb.push(items[nI+(A_Index-1)]) ; Add next item according to index. (adding one item from items per new combination) nextLevel.push(newComb) ; Store new combination } } level:=nextLevel ; nextLevel is done, set level to nextLevel, repeat... } all.push([items]) ; The last level is trivial, it is the input. return all ; Done. } ; Help function nchoosek(n,k){ ; n!/k!(n-k)!, n>=k>0 m:=n-k,p:=1 loop, % m p*=(n-(A_Index-1))/A_Index return round(p) } ; For visualisation, only suitable for string items combinationToString(combArr,delItem:="",delLevel:="`n"){ for k, level in combArr{ for l, items in level { for m, item in items str.=item . delItem str:=rtrim(str,delItem) . delLevel } } return trim(str,delLevel) }
Now, reading littlegandhi1199 s explanation I think this is the same idea. However, @littlegandhi1199, regarding repetions, there are no repetions for unique items, but if items are not unique you get repetions. So you will have to sort that out anyways, as wolf_II have noticed here. I think your implemention is correct there wolf_II, in my implemention, I worked with strings, not arrays, then I do Sort, result, U to remove duplicates.
Sorry for the long post
Have fun and good luck wolf. I will try to understand Helgef, because I'm sure those comments only benefit me so I thank you! Still very annoying that pre-perfection his is somehow faster. I suppose some functions are just faster then simple array lookups..wolf_II wrote:@Helgef: I was too tired to realize what I did and didn't do. When I woke up, somehow I knew exactly why I get repetitions with input=ABBA. Cause the repeated letters of the input. D'oh. Those can't possibly be avoided, They MUST be filtered. Then I checked for responses in this thread, and there it was: "if items are not unique you get repetitions. So you will have to sort that out anyway".
I need some time to read your general solution, I will implement the hiding of the Listbox when updating it, I will check out sort, result, U and and and ...
Thank you.
I write some more in this thread, but I want to write code first.
Code: Select all
GuiControl, hide, LBox
GuiControl,, LBox, % "|" (WordList ? WordList : "no anagrams for " String)
GuiControl, show, LBox
Code: Select all
Keyword := make_Keyword(NextShorter)
Code: Select all
AdjLength := StrLen(KeyWord) // 2 + 1
I have seen in the past questions about this in the forum, I think maybe the docs would benefit from an example like:docs wrote:Retrieves the count of how many characters are in a string.
Code: Select all
; ANSI string
AString := "abdc"
MsgBox, % AString "`n`n" StrLen(AString)
; Unicode string
WString := "ШЙфЖ"
MsgBox, % WString "`n`n" StrLen(WString)
I love when that happens
Code: Select all
;-------------------------------------------------------------------------------
Combinations(String) { ; return an array with all the combinations of String
;-------------------------------------------------------------------------------
If (Len := StrLen(String)) = 1
Return, [String]
Store := [], Result := []
Loop, %Len% {
; split off a single letter
Front := SubStr(String, A_Index, 1)
Back := SubStr(String, A_Index + 1)
; deal with Front, single letter is its own keyword
If Not Store.HasKey(Front) {
Store[Front] := 1
Result.Push(Front)
}
; deal with Back, use recursion
For each, SubString in Combinations(Back) {
Key := make_Keyword(Front SubString)
If Not Store.HasKey(Key) {
Store[Key] := 1
Result.Push(Front SubString)
}
}
}
Return, Result
}
Code: Select all
#NoEnv
#SingleInstance, Force
start := QPC()
Num_1 := nchoosek(50, 5)
T1 := QPC() - Start
start := QPC()
Num_2 := Choose(50, 5)
T2 := QPC() - Start
MsgBox, % Num_1 " - " T1 "s`n" Num_2 " - " T2 "s`n"
ExitApp
;-------------------------------------------------------------------------------
nchoosek(n,k){
; n!/k!(n-k)!, n>=k>0
m:=n-k,p:=1
loop, % m
p*=(n-(A_Index-1))/A_Index
return round(p)
}
;-------------------------------------------------------------------------------
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
}
;-------------------------------------------------------------------------------
QPC() { ; microseconds precision
;-------------------------------------------------------------------------------
static Freq, init := DllCall("QueryPerformanceFrequency", "Int64P", Freq)
DllCall("QueryPerformanceCounter", "Int64P", Count)
Return, Count / Freq
}
Code: Select all
AdjLength := StrLen(KeyWord) // 2 + 1
Code: Select all
I need the keyword for If Not Store[n].HasKey(Keyword)
Code: Select all
For each, Keyword in Combinations(String) {
AdjLength := StrLen(Keyword) // 2 + 1 ; KeyWord has "," in it, so we need to adjust the string length
For each, Anagram in DICT[AdjLength, Keyword]
WordList .= WordList ? "|" Anagram : Anagram, Count++
}
I'm not entirely sure I did"I'm never entirely sure"
Very good, yours is much better, I just looked up the formula (I can never remember) and typed it in, quick test on a few numbers and it seemed ok. Thanks for catching, I will steal yours.wolf_II wrote:I have written a "n choose k" function lately, which avoids floats by separating the division from the multiplication.
Code: Select all
; ...
For each, Keyword in Combinations(String) {
AdjLength := StrLen(Keyword) // 2 + 1
For each, Anagram in DICT[AdjLength, Keyword]
WordList .= WordList ? "|" Anagram : Anagram, Count++
}
; ...
;-------------------------------------------------------------------------------
Combinations(String) { ; return an array with the KEYWORDS of all the combinations of String
;-------------------------------------------------------------------------------
; ...
; deal with Back, use recursion
For each, Keyword in Combinations(Back) {
Key := make_Keyword(Front StrReplace(Keyword, ",")) ; here I have to "undo the keyword", prepend the Front part, and then redo it
;~ MsgBox, % Key
If Not Store.HasKey(Key) {
Store[Key] := 1
Result.Push(Key)
}
}
; ...
I can not confirm that, sorry.There is some noise in the result too it seems, for "abcd" I get one item "abcda"
Code: Select all
#NoEnv
SetBatchLines, -1
FileRead, WordsList, %A_ScriptDir%\words_alpha.txt
Delim := Chr(1)
WordsList := RegExReplace(WordsList, "([^`r`n])", "$1" . Delim)
Words := []
Loop, Parse, WordsList, `n, `r
{
w := StrReplace(s := A_LoopField, Delim)
Sort, s, D%Delim%
s := StrSplit(s . "__", Delim)
if (Words[s*]) != ""
Words[s*].Push(w)
else
Words[s*] := [w]
}
WordsList := ""
; Done making 'Words' object.
Loop {
InputBox, OutputVar, Anagrams, Enter a word.
if (ErrorLevel != 0)
return
Anagrams := "", Combos := []
Combos[StrLen(OutputVar), SortWord(OutputVar)] := true
Combinations(OutputVar, Combos)
while x := Combos.MaxIndex() {
for key, val in Combos.Pop() {
for i, v in Words[StrSplit(key . "__", Delim)*]
Anagrams .= v "`r`n"
}
}
MsgBox, 64, Anagrams, % Anagrams
}
return
SortWord(Word) {
static Delim := Chr(1)
Word := RegExReplace(Word, "(.)", "$1" . Delim)
Sort, Word, D%Delim%
return Word
}
Combinations(Str, Arr, Depth:=3) {
if (Depth < 1 || Str = "")
return
Loop, % Len := StrLen(Str) {
s := SubStr(Str, 1, A_Index - 1) . SubStr(Str, A_Index + 1)
Arr[Len - 1, SortWord(s)] := true
Combinations(s, Arr, Depth - 1)
}
}
My initial testing was positive, v 1.18 seems like an improvement, although slight. Results may ofc vary between different strings, that is a good observation.wolf_II wrote:version 1.18
Edit: Time measurements with input = "thequickbrownfox" show Combinations(String) takes about 2 seconds (was about 1 second with v1.17)
Recursion is nice and readable, but slow. Helgef said so already, I just post my measurements.
Code: Select all
;-------------------------------------------------------------------------------
Combine(n, k) { ; number of combinations with repetitions
;-------------------------------------------------------------------------------
; e.g.: number of ways to combine 2 letters from 4 given letters
;
; we are allowed to choose the same letter multiple times,
; but the order we choose them does not matter
;
; given: ABCD, possibilities: AA, AB, AC, AD, BB, BC, BD, CC, CD, DD
;---------------------------------------------------------------------------
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
}
;-------------------------------------------------------------------------------
Power(n, k) { ; return n**k, number of permutations with repetitions
;-------------------------------------------------------------------------------
; e.g. number of different ways to toss a coin three times in a row
; H = heads, T = tails
; possibilities: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT
;---------------------------------------------------------------------------
Return, n**k
}
;-------------------------------------------------------------------------------
Factorial(n) { ; returns n!, number of permutations without repetitions
;-------------------------------------------------------------------------------
; e.g. number of different ways to draw three coloured marbles out of a hat
; given: B = blue, G = green, Y = yellow
; possibilities: BGY, BYG, GBY, GYB, YBG, YGB
;---------------------------------------------------------------------------
; factorials of negative integers are undefined
; factorials of 21 or bigger overflow an Int64
If n between 0 and 20
{
Result := 1
Loop, %n%
Result *= A_Index
Return, Result
}
}
Code: Select all
Obj := []
Obj["a", "b"] := ["ab", "ba"]
Obj["a", "b", "c"] := ["abc", "cab"]
for key, val in Obj["a", "b"]
x .= "<" val ">`n"
MsgBox, % x
Obj := [], x := ""
Obj["a", "b", "__"] := ["ab", "ba"]
Obj["a", "b", "c", "__"] := ["abc", "cab"]
for key, val in Obj["a", "b", "__"]
x .= "<" val ">`n"
MsgBox, % x
Code: Select all
#NoEnv
SetBatchLines, -1
#SingleInstance, force
FileRead, WordsList, words.txt ; change this if needed
Delim := Chr(1)
WordsList := RegExReplace(WordsList, "([^`r`n])", "$1" . Delim)
Words := []
Loop, Parse, WordsList, `n, `r
{
w := StrReplace(s := A_LoopField, Delim)
Sort, s, D%Delim%
s := StrSplit(s . "_", Delim)
if (Words[s*]) != ""
Words[s*].Push(w)
else
Words[s*] := [w]
}
WordsList := ""
; Done making 'Words' object.
Loop {
InputBox, OutputVar, Anagrams, Enter a word.`nResult is put in clipboard`nCancel - Exitapp
if (ErrorLevel != 0)
Exitapp
ctr:=0
Anagrams := "", Combos := []
OutputVar:=SortWord(OutputVar) ; <-- so input can be permutated
Combos[StrLen(OutputVar), OutputVar] := true
; Combinations(OutputVar, Combos, (sl:=strlen(OutputVar))>4?sl-4:sl) ;alt, skip short ones.
Combinations(OutputVar, Combos, strlen(OutputVar)) ; changed depth to get all.
while x := Combos.MaxIndex() {
for key, val in Combos.Pop() {
for i, v in Words[StrSplit(key . "_")*]
Anagrams .= v "`r`n", ctr++
}
}
clipboard:=Anagrams ; <-- result to clipboard
MsgBox, 64, Anagrams, % "found: " ctr
}
return
SortWord(Word) {
static Delim := Chr(1)
Word := RegExReplace(Word, "(.)", "$1" . Delim)
Sort, Word, D%Delim%
return strreplace(Word,delim) ; <-- added
}
Combinations(Str, Arr, Depth:=3) {
if (Depth < 1 || Str = "")
return
Loop, % Len := StrLen(Str) {
s := SubStr(Str, 1, A_Index - 1) . SubStr(Str, A_Index + 1)
Arr[Len - 1, s] := true ; edit
Combinations(s, Arr, Depth - 1)
}
}
Code: Select all
;-------------------------------------------------------------------------------
Combinations(String) { ; return an array with the KEYWORDS of all the combinations of String
;-------------------------------------------------------------------------------
Keyword := make_Keyword(String) ; the only call here to make_Keyword()
Store := []
Store[0] := []
Store[0, Keyword] := True
Result := [Keyword]
Loop, % (Len := StrLen(String)) - 1 {
Store[n := A_Index] := [] ; array of n* shortened strings
For ShortKey in Store[n - 1] {
Loop, % StrLen(ShortKey) // 2 + 1 {
; split the ShortKey and get next shorter keyword
Split1 := SubStr(ShortKey, 1, 2 * A_Index - 2) ; keep delim
Split3 := SubStr(ShortKey, 2 * A_Index + 1) ; drop delim
NextShorter := RTrim(Split1 Split3, ",") ; trim delim
If Not Store[n].HasKey(NextShorter) {
Store[n, NextShorter] := True
Result.Push(NextShorter)
}
}
}
}
Return, Result
}
I like to try to apply the idea to v1.18 (building up to full string) as well now. Since it involves "minimal effort" it might take me 24 hours again.Helgef wrote:Also, in v 1.18, there is minimal effort to reduce the number of calls to make_keyword()
Yes that would work provided you could guarantee that the character would not be in any word.Helgef wrote:Thank you very much for you explanation kon. I think I get it, but I do not get why it need be strlen>1 in this case, it would suffice it is not a letter, right?
The version I posed above does find police with the input 'epolic'. Perhaps I misunderstand. Good call sorting the string before sending it to Combinations();that was a glaring oversight on my part. I didn't test speed, but it will surely be an improvement.Helgef wrote:I make a small modification to to allow permutated input, eg, we find all anagrams for
police even if we type epolic.
Thanks. Instead of a limit on the length of the input string, the limit is on the depth of recursion. I thought the stated goal of the OP was not to find ALL matches. ie: "My goal is to write the script such that it would display for example, possible 7- or 8-letter solutions for any given 9-letter string." I may have missed some discussion where it was decided to find ALL combinations, but I thought I would just point out the advantage for longer strings. ie: strlen>22 is still instant, provided the depth of recursion is limited.Helgef wrote:Very nicely done kon, it is short and sweet, if it where not for the recursion, this would be the fastest one I am sure.
Indeed it does, my mistakekon wrote:The version I posed above does find police with the input 'epolic'.
Indeed, our ambitions grew in parallel with our greed.I may have missed some discussion where it was decided to find ALL combinations
Very good, and you did find out where to call make_keywordwolf_II wrote:v1.19 - 0.415 seconds
Code: Select all
;-------------------------------------------------------------------------------
Combinations(String) { ; return an array with the "sub-keywords" of String
;-------------------------------------------------------------------------------
; sub-keywords are the keywords of all the substrings of String
;---------------------------------------------------------------------------
If (Len := StrLen(String)) = 1
Return, [String]
Keyword := make_Keyword(String)
Store := [], Result := []
Loop, %Len% {
; split off a single letter
Front := SubStr(Keyword, 2 * A_Index - 1, 1)
Back := SubStr(Keyword, 2 * A_Index + 1)
; deal with Front, single letter is its own keyword
If Not Store.HasKey(Front) {
Store[Front] := True
Result.Push(Front)
}
; use recursion to deal with Back, argument expects a string
For each, ShortKey in Combinations(StrReplace(Back, ",")) {
Key := Front "," ShortKey
If Not Store.HasKey(Key) {
Store[Key] := True
Result.Push(Key)
}
}
}
Return, Result
}
Code: Select all
Exclude words of length: [1,2 .., show all.]
Return to “Gaming Scripts (v1)”
Users browsing this forum: No registered users and 6 guests