nickollio28 / trie-and-combination-finder

Finds all combinations of English words that are 5 letters long, where no letters are repeated.

Trie and Combination Finder

This code defines a Trie data structure and a function to find combinations of 5 words that do not share any common letters.

Trie

A Trie (prefix tree) is a tree-like data structure that is used to store a set of words. Each node in the Trie represents a letter in a word. The root node represents an empty string and the child nodes represent the letters in the word. The Trie has a flag called 'is_word' that indicates whether the word represented by the path from the root node to the current node is a word in the set.

The Trie data structure is useful for searching for words in a large dataset because it allows you to search for words that start with a given prefix.

find_combinations function

The find_combinations function searches for combinations of 5 words using a depth-first search. It starts from the given prefix and checks if it is a word. If it is a word, it is added to the current combination. If the current combination has 5 words, it is added to the list of combinations. If the current combination does not have 5 words, the search continues by adding each letter of the current prefix to the current word and recursively calling the function. If the current prefix is not a word, the search continues by adding each letter of the current prefix to the current word and recursively calling the function.

This function uses the tqdm library to display a progress bar, and the concurrent.futures module to parallelize the search using a ProcessPoolExecutor.

Dependencies

• json
• tqdm
• concurrent.futures

Usage

To use the Trie and find_combinations function, you will need to create a Trie object and insert the words you want to search for into the Trie. Then, you can call the find_combinations function with the Trie and the prefix you want to start the search from.

Here is an example of how you can use the Trie and find_combinations function:

import json
from tqdm import tqdm
from concurrent.futures import ProcessPoolExecutor

# Create a Trie object
trie = Trie()

# Insert some words into the Trie
trie.insert('cat')
trie.insert('car')
trie.insert('bat')
trie.insert('bar')
trie.insert('rat')
trie.insert('rar')

# Find combinations of 5 words that do not share any common letters
combinations = find_combinations(trie, '', '', (), [])

# Print the combinations
print(combinations)

This will output the following list of combinations:

[('bat', 'car', 'rat', 'rar', 'cat'), ('bat', 'car', 'rat', 'rar', 'bar')]

References

• Trie - Wikipedia
• tqdm - Fast, Extensible Progress Bar for Python and CLI
• concurrent.futures - Executor-based parallelism