recursive function for wordsearch

Question

given letters: example of letters

letters = 'hutfb' 

I am given a file with a list of words.

I need to write a recursive function that allows me to check all possibilities the letters can make. If the possibility is in the list of words from the file, I need to print that specific word.

so for letters given

they can create the words:

• a
• cat
• ac
• act
• cab

and so on and on

each combination the letters make I need to check the file to see if its a valid word. if it is I need to print them.

I don't know how start to write this function.

Answer 1

Unfortunately I cannot help just now with a recursive function, but given that a higher count of letters/characters can easily explode into billions of potential combinations if not filtered during creation I have a quirky alternative by iterating over the known words. Those have to be in memory anyway.

[EDIT] Removed the sorting as it does not really provide any benefit, fixed an issue where I falsely set to true on iteration

# Some letters, separated by space
letters = 'c a t b'
# letters = 't t a c b'

# # Assuming a word per line, this is the code to read it
# with open("words_on_file.txt", "r") as words:
#     words_to_look_for = [x.strip() for x in words]
#     print(words_to_look_for)

# Alternative for quick test
known_words = [
    'cat',
    'bat',
    'a',
    'cab',
    'superman',
    'ac',
    'act',
    'grumpycat',
    'zoo',
    'tab'
]

# Create a list of chars by splitting
list_letters = letters.split(" ")

for word in known_words:
    # Create a list of chars
    list_word = list(word)
    if len(list_word) > len(list_letters):
        # We cannot have longer words than we have count of letters
        # print(word, "too long, skipping")
        continue

    # Now iterate over the chars in the word and see if we have
    # enough chars/letters
    temp_letters = list_letters[:]

    # This was originally False as default, but if we iterate over each
    # letter of the word and succeed we have a match
    found = True
    for char in list_word:
        # print(char)
        if char in temp_letters:
            # Remove char so it cannot match again
            # list.remove() takes only the first found
            temp_letters.remove(char)
        else:
            # print(char, "not available")
            found = False
            break

    if found is True:
        print(word)

You could copy&paste a product function from the itertools documentation and use the code provided by ExtinctSpecie, it has no further dependencies, however I found without tweaking it returns all potential options including duplications of characters which I did not immediately understand.

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Answer 2

I agree with @dparolin about processing the words file to see if words conform to the letters, not generating possible words and seeing if they are in the file. This allows us not to read the file into memory, as we only need to examine one word at a time. And it can be done with a recursive test:

letters = 'catbt'

def is_match(letters, word):

    if not word:
        return True

    if not letters:
        return False

    letter = letters.pop()

    if letter in word:
        word.remove(letter)

    return is_match(letters, word)

with open('words.txt') as words:
    for word in words:
        word = word.strip()

        if is_match(list(letters), list(word)):
            print(word)

EXAMPLE USAGE

% python3 test.py
act
at
bat
cab
cat
tab
tact
%

And we should be able to work with lots of letters without issue.

Answer 3

import itertools
str = "c a t b"
letters = list(str.replace(" ",""))
words_to_look_for = []

for index, letter in enumerate(letters):
    keywords = [''.join(i) for i in itertools.product(letters, repeat = index+1)]
    words_to_look_for.extend(keywords)

print(words_to_look_for)

https://stackoverflow.com/questions/7074051/....

Answer 4

As noted above, this will not be feasible for any more than the number of letters countable on your two hands. There's just too many possibilities to check. But if you were to try this, here's how the code would look.

letters = ['a', 'b', 'c']

def powerset(letters):
    output = [set()]
    for x in letters:
        output.extend([y.union({x}) for y in output])
    return output

for subset in powerset(letters):
    for potential_word in map(''.join, itertools.permutations(list(subset))):
        # Check if potential_word is a word

This won't try words with duplicate letters (that would be another layer of insanity), but it will try all possible potential words that could be formed by a subset of the letters you give in any order.

[edit] Just realized you requested a recursive solution. Dunno if that's required or not, but the powerset function could be changed to be recursive. I think that would make it uglier and harder to comprehend, though.