Mailing List Archive: Re: Find 6-letter words that are hidden (embedded) within

Re: Find 6-letter words that are hidden (embedded) within

Feb 24, 2023, 10:59 AM

Post #1 of 4 (159 views)

On 24/02/2023 18:34, Hen Hanna wrote:
>
> i just wrote a program, which...
> within [FunFunPython]
> finds: (funny, futon, python)
>
> ( 5- and 6- letter words )
>
>
> (my program uses a Trie, but is pretty simple)
>
>
>
> Maybe someone would show me
> how it's done using itertools, Permutations, etc.
>
> Wouldn't it get too slow for Letter-Seeds longer than 11 letters or so?
>

For performance, generally you sort the characters in a word to create a
new word (character list) and compare the sorted character lists (which
you can use a string for). Two anagrams will produce the same sorted
character list.

The problem with going through all permutations is that the number of
permutations tends to grow exponentially, so that is why you sort first.

So first take an English dictionary and build a python dictionary with
the key being the character sorted list and the value being a list of
the English words that produce the sorted list, aka anagrams.

You then sort your specific word and test each subset of this sorted
word (each combination of characters) against your python anagram
dictionary.

--
https://mail.python.org/mailman/listinfo/python-list

Re: Find 6-letter words that are hidden (embedded) within [ In reply to ]

henhanna at gmail

Feb 24, 2023, 12:15 PM

Post #2 of 4 (159 views)

Permalink

On Friday, February 24, 2023 at 10:34:31?AM UTC-8, Hen Hanna wrote:
> i just wrote a program, which...
> within [FunFunPython]
> finds: (funny, futon, python)
>
> ( 5- and 6- letter words )
>
>
> (my program uses a Trie, but is pretty simple)
>
>
>
> Maybe someone would show me
> how it's done using itertools, Permutations, etc.
>
> Wouldn't it get too slow for Letter-Seeds longer than 11 letters or so?
>
>
> ______________________
>
> Find 6-letter words that are hidden (embedded) within each row of letters.
> The letters are in the correct order.
>
> 1. JSOYOMFUBELR
> 2. SCDUARWDRLYE
> 3. DASNAGEFERTY
> 4. CLULOOTSCEHN
> 5. USENEARSEYNE

> The letters are in the correct order. -------- So this problem is not about Anagraming.

it seems that
https://docs.python.org/3/library/itertools.html
doesn't offer waht i want, so i wrote this (below) and it works.

Is there a better or faster way to do the same thing?

def subs( x ):
if x=='': return ['']
x1= subs( x[1:] )
return x1 + mapAdd(x[0] , x1)

def mapAdd( x, Ylis ): return [ x+y for y in Ylis ]

print( subs('ab' ))
print( subs('abc' ))
--
https://mail.python.org/mailman/listinfo/python-list

RE: Find 6-letter words that are hidden (embedded) within [ In reply to ]

David.Raymond at tomtom

Feb 24, 2023, 1:16 PM

Post #3 of 4 (159 views)

Permalink

> Find 6-letter words that are hidden (embedded) within each row of letters.
> The letters are in the correct order.
>
> 1. JSOYOMFUBELR
> 2. SCDUARWDRLYE
> 3. DASNAGEFERTY
> 4. CLULOOTSCEHN
> 5. USENEARSEYNE

> The letters are in the correct order. -------- So this problem is not about Anagraming.

You can get every combination of 6 letters out of it with itertools.combinations like below.
Just implement the isWord function to return whether a string actually counts as a legit word or not.
12 choose 6 is only 924 combinations to check, so shouldn't be too bad to check them all.

def isWord(word):
return True #Best left as an exercise to the reader

startWord = "JSOYOMFUBELR"
subLetterCount = 6

foundWords = set()

for letters in itertools.combinations(startWord, subLetterCount):
word = "".join(letters)
if word not in foundWords and isWord(word):
print(word)
foundWords.add(word)
--
https://mail.python.org/mailman/listinfo/python-list

Re: Find 6-letter words that are hidden (embedded) within [ In reply to ]

henhanna at gmail

Feb 24, 2023, 3:49 PM

Post #4 of 4 (159 views)

Permalink

On Friday, February 24, 2023 at 1:18:28?PM UTC-8, David Raymond wrote:
> > Find 6-letter words that are hidden (embedded) within each row of letters.
> > The letters are in the correct order.
> >
> > 1. JSOYOMFUBELR
> > 2. SCDUARWDRLYE
> > 3. DASNAGEFERTY
> > 4. CLULOOTSCEHN
> > 5. USENEARSEYNE
>
> > The letters are in the correct order. -------- So this problem is not about Anagraming.
> You can get every combination of 6 letters out of it with itertools.combinations like below.
> Just implement the isWord function to return whether a string actually counts as a legit word or not.
> 12 choose 6 is only 924 combinations to check, so shouldn't be too bad to check them all.
>
>
> def isWord(word):
> return True #Best left as an exercise to the reader
>
> startWord = "JSOYOMFUBELR"
> subLetterCount = 6
>
> foundWords = set()
>
> for letters in itertools.combinations(startWord, subLetterCount):
> word = "".join(letters)
> if word not in foundWords and isWord(word):
> print(word)
> foundWords.add(word)

thank you... i could use the Pset below, too.

# Factorial Python One-Liner
def fac(n): return reduce(lambda x, y: x * y, range(1, n+1))

for i in range(1,11): print ( '\t', fac(i) )

# Power set Python One-Liner
def Pset(L): return reduce(lambda z, x: z + [y + [x] for y in z], L, [[]])

print( '\n', Pset( [1,] ))
print( '\n', Pset( [1,2,] ))
print( '\n', Pset( [1,2,3] ))
--
https://mail.python.org/mailman/listinfo/python-list