Hello. I have several comments.
First,
Helgef wrote:I see little need to improve something that works more or less instantly, in a on-user-typing context.
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.
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 line
Code: Select all
GuiControl,, LBox, % "|" (WordList ? WordList : "no anagrams for " String)
takes almost half a second
however,
Code: Select all
GuiControl, hide, LBox
GuiControl,, LBox, % "|" (WordList ? WordList : "no anagrams for " String)
GuiControl, show, LBox
takes
~150 ms, simple improvment!
Here are my measurments, for input string
"abcdefghijklmnop", 16 letters,
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.
So
combinations() is the culprit, no surprise really. The
sort we needn't think about.
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 do
Code: Select all
Keyword := make_Keyword(NextShorter)
but then return
NextShorter and then you do
Code: Select all
Keyword := make_Keyword(SubString)
again, you could return the KeyWord instead, its not gonna save you but still it is a bit wasteful. Note, then you need
Code: Select all
AdjLength := StrLen(KeyWord) // 2 + 1
for correct lookups. (I think
)
Regarding the algorithm, during the
no-spoiler period, I did implement a
general combination function,
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)
}
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
.
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