Anagrams for TV show "Countdown"

[wolf_II]

Maybe offtopic, but closely related:
I have made an attempt at getting all permutations of a word (anagram candidates?) and I wonder: Is there a clever way to do that?
I use a stupid-brute-force recursive approach, which returns n! (factorial) members (unsorted, allows repeats) in an array.

Example:

• (Word length = 8) => get permutations in 0.2 sec, dict lookup = 0.02 sec
• (Word length = 9) => get permutations in 6.3 sec, dict lookup = 0.2 sec
• (Word length = 10) => get permutations in 480 sec, dict lookup = 2 sec

There must be a better way?!

Permutations()

Code: Select all

;-------------------------------------------------------------------------------
Permutations(Word) { ; return array with all permutations of Word
;-------------------------------------------------------------------------------
    If (Len := StrLen(Word)) = 1
        Return, [Word]

    Result := []
    Loop, %Len% {

        Split1 := SubStr(Word, 1, A_Index - 1)      ; before pos
        Split2 := SubStr(Word, A_Index, 1)          ; at pos
        Split3 := SubStr(Word, A_Index + 1)         ; after pos

        If StrLen(Split1 Split3)
            For each, Perm in Permutations(Split1 Split3)
                Result.Push(Split2 Perm)
    }

    Return, Result
}

Edit: corrected typo

[Helgef]

That is a nice function wolf_II.
Although I'm not sure I like the permutation + look-up method for finding anagrams. At least one should have separate dictionaries for each word length.

[Helgef]

Suggestion, make a list of all anagrams, then look up in that list, you only have to do it once.

Code: Select all

setbatchlines,-1
listlines,off
#noenv
dictionary=
(
Bruce
Arnold
ceBru
Dolph
Dollp
Chuck
Chukc
Cuhkc
)
dict:=[]
Loop, Parse, dictionary, `n, `r 							; Put all words in an array dict, at dict[wordLength, wordLettersSorted, entryNumber]
{
	keyword:=A_LoopField
	len:=strlen(A_LoopField)
	keyword:=Ltrim(RegExReplace(keyword,"(.)",",$1"),",")
	Sort,keyword,D,											; Make a keyword, eg, Dallas -> a,a,D,l,l,s
	if !IsObject(dict[len,keyword])
		dict[len,keyword]:=[]
	dict[len,keyword].push(A_LoopField)						; Put the word in the keyword slot, all permutations will get the same keyword and end up in this slot
}
allAnagrams:=[]
for len, lengthGroup in dict {
	for keyword, anagrams in lengthGroup
		if (anagrams.length()>1)							; For each keyword which has more than entry, there is anagrams, save those
			allAnagrams.push(anagrams)
}
str:="Anagram list:`n"										; Print result
for k, anagrams in allAnagrams {
	str.= "Anagram set`t" k ":`t"
	for l, anagram in anagrams
		str.=anagram  "`t" 
	str.= "`n" 
}
gui, font,,courier new										; Show result
gui,add,edit,w1000 r40, % str
gui,show

Edit: The len key in dict only serves the purpose of getting the list in descending length order, you can remove it if you want.
Edit 2: Results, found 7577 anagram sets in ~1.3 seconds,

result.txt

(276.02 KiB) Downloaded 59 times

Searched in wordlist consisting of circa 100000 words:

wl2.txt

(1020.27 KiB) Downloaded 56 times

Example,

Code: Select all

Anagram set	2106:	capers	casper	crapes	escarp	pacers	parsec	recaps	scrape	spacer	

[wolf_II]

(written before Helgef's most recent post)
Are you talking personal preference or raw performance?
In case I can not improve the (most significant) Permutations() function, How much of a benefit would you expect?
My test with WordLength = 9 doesn't show much benefit (dictionary text file has 370,101 words, max length = 31).
T1 (get permutation) still 6.0 sec, T2 (lookup) still 0.2 sec

[wolf_II]

Blimey, I think I get it now! Holy Handgranade, this is awsome.
You are not calculating permutations, you just make the dictionary your bitch. (sorry for foul language)

I am ... speechless.


Thank you for sharing this.

[wolf_II]

@littlegandhi1199: Sorry for hijacking your thread.

Anagrams.ahk

This script takes about five second to load (not measured accurately, though). The results are then displayed immediately.

Code: Select all

;-------------------------------------------------------------------------------
; Anagrams.ahk
; by wolf_II
;-------------------------------------------------------------------------------
; simple Anagram searcher
; written with massive help by Helgef from AHK forum
; https://autohotkey.com/boards/viewtopic.php?p=158284#p158284
;-------------------------------------------------------------------------------



;-------------------------------------------------------------------------------
AutoExecute: ; auto-execute section of the script
;-------------------------------------------------------------------------------
    #NoEnv                              ; don't check empty variables
    #SingleInstance, Force              ; kill old instance
    ;---------------------------------------------------------------------------
    SetBatchLines, -1                   ; run script at maximum speed
    ;===========================================================================
    SetWorkingDir, %A_ScriptDir%        ; consistent directory
    SplitPath, A_ScriptName,,,, AppName ; get AppName from file name
    ;---------------------------------------------------------------------------
    Version := "1.05"
    ;===========================================================================

    ; GUI
    Gui, New, -MinimizeBox, %AppName% v%Version%
    Gui, Add, Edit, w100 vWord gCountLetters Disabled, Loading ...
    Gui, Add, Button, x+m yp-1 wp Default Disabled, get Anagrams
    Gui, Add, ListBox, xm r10 w210 vLBox
    Gui, Add, StatusBar
    SB_SetParts(60)
    SB_SetText("Length:", 1)
    SB_SetText("Count:", 2)
    Gui, Show

    ; https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt
    FileRead, Dictionary, words_alpha.txt

    DICT := []
    Loop, Parse, Dictionary, `n, `r
    {
        WordLength := StrLen(A_LoopField)
        If Not IsObject(DICT[WordLength])
            DICT[WordLength] := []

        StringLower, Keyword, A_LoopField
        Keyword := make_Keyword(Keyword)
        If Not IsObject(DICT[WordLength, Keyword])
            DICT[WordLength, Keyword] := []

        DICT[WordLength, Keyword].Push(A_LoopField)
    }

    GuiControl, Enable, Word
    GuiControl,, Word
    GuiControl, Focus, Word
    GuiControl, Enable, Button1

Return ; end of auto-execute section



GuiClose:
ExitApp



;-------------------------------------------------------------------------------
CountLetters: ; live display
;-------------------------------------------------------------------------------
    GuiControlGet, Word
    SB_SetText("Length: " WordLength := StrLen(Word), 1)

Return



;-------------------------------------------------------------------------------
ButtonGetAnagrams: ; display all anagrams of Word found in Dictionary
;-------------------------------------------------------------------------------
    GuiControl, Focus, Word
    GuiControl, Disable, Button1
    GuiControl,, LBox, |
    SB_SetText("Count:", 2)

    Keyword := make_Keyword(Word), WordList := "", Count := 0
    For each, Anagram in DICT[WordLength, Keyword]
        WordList .= WordList ? "|" Anagram : Anagram, Count++

    GuiControl,, LBox, % WordList ? WordList : "no anagrams for " Word
    SB_SetText("Count: " Count, 2)
    GuiControl, Enable, Button1

Return



;-------------------------------------------------------------------------------
make_Keyword(Word) { ; return a sorted, comma separated string of chars
;-------------------------------------------------------------------------------
    Keyword := LTrim(RegExReplace(Word, "(.)", ",$1"), ",")
    Sort, Keyword, D,
    Return, Keyword
}



/*--------- end of file --------------------------------------------------------

[Helgef]

Nice script
It performs well enough to have a live search, added gosub

Code: Select all

;-------------------------------------------------------------------------------
CountLetters: ; live display
;-------------------------------------------------------------------------------
	GuiControlGet, Word
	SB_SetText("Length: " WordLength := StrLen(Word), 1)
	Gosub, ButtonGetAnagrams
Return

This will give false results, for example when you type dda it will list add and dad, but that could be considered a feature. I.e, given a permutation of letters, find all real word anagrams for it.

[wolf_II]

@Helgef: I have taken out the button completely, thanks for the suggestion. My original code does not even resemble the current script any longer.
And we are definitely off topic now, no more RegExMatch(), very much explored alternatives though. I hope that counts.

Re. feature: The thought never crossed my mind, that Input might not be a valid word, I took it for granted, that it wouldn't. I was thinking about a TV Show called "Countdown", but my script would not be able to find a 7 or 8 letter word from any given 9 letters. For now, let's call it a feature of the script, with a TODO item?

EDIT:
And that brings back the question: Can a Permutations() function be made faster than O(n^2) I'm not even sure it's O(n^2), I only know it's bad. It might be O(n!) if such a thing exists.

EDIT2: I reported my first post in this thread as off topic, and hope the discussion that followed afterwards will be moved to a separate thread. I don't wish to annoy any futher, but I wish to continue the discussion. I hope that's OK for everybody?

Version 1.06

Code: Select all

;-------------------------------------------------------------------------------
; Anagrams.ahk
; by wolf_II
;-------------------------------------------------------------------------------
; simple Anagram searcher
; written with massive help by Helgef from AHK forum
; https://autohotkey.com/boards/viewtopic.php?p=158284#p158284
;-------------------------------------------------------------------------------



;-------------------------------------------------------------------------------
AutoExecute: ; auto-execute section of the script
;-------------------------------------------------------------------------------
    #NoEnv                              ; don't check empty variables
    #SingleInstance, Force              ; kill old instance
    ;---------------------------------------------------------------------------
    SetBatchLines, -1                   ; run script at maximum speed
    SetWorkingDir, %A_ScriptDir%        ; consistent directory
    SplitPath, A_ScriptName,,,, AppName ; get AppName from file name
    ;===========================================================================

    Version := "1.06"

    ; GUI
    Gui, New, -MinimizeBox, %AppName% v%Version%
    Gui, Add, Edit, w100 vWord gShowAnagrams Disabled, Loading ...
    Gui, Add, ListBox, xm r10 w210 vLBox
    Gui, Add, StatusBar
    SB_SetParts(60)
    SB_SetText("Length:", 1)
    SB_SetText("Count:", 2)
    Gui, Show

    ; https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt
    FileRead, Dictionary, words_alpha.txt

    DICT := []
    Loop, Parse, Dictionary, `n, `r
    {
        WordLength := StrLen(A_LoopField)
        If Not IsObject(DICT[WordLength])
            DICT[WordLength] := []

        StringLower, Keyword, A_LoopField
        Keyword := make_Keyword(Keyword)
        If Not IsObject(DICT[WordLength, Keyword])
            DICT[WordLength, Keyword] := []

        DICT[WordLength, Keyword].Push(A_LoopField)
    }

    GuiControl, Enable, Word
    GuiControl, Focus, Word
    GuiControl,, Word

Return ; end of auto-execute section



GuiClose:
ExitApp



;-------------------------------------------------------------------------------
ShowAnagrams: ; live display all anagrams of Word found in Dictionary
;-------------------------------------------------------------------------------
    GuiControlGet, Word
    WordLength := StrLen(Word)

    Keyword := make_Keyword(Word), WordList := "", Count := 0
    For each, Anagram in DICT[WordLength, Keyword]
        WordList .= WordList ? "|" Anagram : Anagram, Count++

    GuiControl,, LBox, % "|" (WordList ?  WordList : "no anagrams for " Word)
    SB_SetText("Length: " WordLength, 1)
    SB_SetText("Count: " Count, 2)

Return



;-------------------------------------------------------------------------------
make_Keyword(Word) { ; return a sorted, comma separated string of chars
;-------------------------------------------------------------------------------
    Keyword := LTrim(RegExReplace(Word, "(.)", ",$1"), ",")
    Sort, Keyword, D,
    Return, Keyword
}



/*--------- end of file --------------------------------------------------------

[Helgef]

I agree there is some off-topic here, sorry
I think Anagrams.ahk should live in Scripts and functions.
Regarding the permutations() function, it is clearly O(n!) w.r.t the number of function calls. However, I have no better ideas, I think it is very nice as is, very readable, and it could live in Scripts and functions too.