CODEWITHSUNDEEP
pythonnlp
Linke
Linke

Reputation: 1

How to find all word combinations from a string and a list of synonyms

I have a list of words where some of these words have a synonym

words = ['cat','under','table']

feline;cat

below;down;under;beneath

table;bench;board

And I need to find different list combinations with these synonyms.

That example would return:

['cat','under','table'],['feline','under','table'],['cat','below','table'],['feline','below','table'] ...

I'm wondering if there is an algorithm that solves this problem. Or how can I deal with it? I tried using a nested loop approach but i have problems because the length of the list of words and list of synonym are variable

Upvotes: 0

Views: 237

Answers (2)

Mo...
Mo...

Reputation: 1961

Using the builtin library (itertools.product)

from itertools import product

for a, b, c in product(
    ["feline", "cat"],
    ["below", "down", "under", "beneth"],
    ["table", "bench", "board"],
):
    print(a, b, c) # feline below table (and so on)

Python implementation

itertools.product is implemented in C, but it's equivalent to the following.

def my_product(*args):

    result = [[]]

    for _list in args:
        result = [x + [y] for x in result for y in _list]

    for item in result:
        yield item


for a, b, c in my_product(
    ["feline", "cat"],
    ["below", "down", "under", "beneth"],
    ["table", "bench", "board"],
):
    print(a, b, c)

Output

Both produce the same output

feline below table
feline below bench
feline below board
feline down table
feline down bench
feline down board
feline under table
feline under bench
feline under board
feline beneth table
feline beneth bench
feline beneth board
cat below table
cat below bench
cat below board
cat down table
cat down bench
cat down board
cat under table
cat under bench
cat under board
cat beneth table
cat beneth bench
cat beneth board

Upvotes: 1

SeoHyeong Jeong
SeoHyeong Jeong

Reputation: 11

You can solve the problem using Python's itertools.product. Here's the way I solved it.

from itertools import product

def solution(words, syn):
    new_words_list = []
    for w in words:
        if w in syn.keys():
            new_words_list.append(syn[w] + [w])
        else:
            new_words_list.append([w])
    answer = list(product(*new_words_list))
    return answer

Given that your words is given as a list of strings and syn is given as a dictionary where the key is a word in the words and value is the list of synonym(s), take words and syn as inputs and generate a nested list called new_words_list of every possible case for each word.

[['feline', 'cat'], ['below', 'down', 'beneath', 'under'], ['bench', 'board', 'table']]

Since the length of words and syn are variables, use a * of list comprehension operation to pass the nested list, new_words_list, to itertools.product(). itertools.product() computes the Cartesian product of given iterables.

The output of this code snippet would be as follows.

['feline', 'below', 'bench']
['feline', 'below', 'board']
['feline', 'below', 'table']
['feline', 'down', 'bench']
['feline', 'down', 'board']
['feline', 'down', 'table']
['feline', 'beneath', 'bench']
['feline', 'beneath', 'board']
['feline', 'beneath', 'table']
['feline', 'under', 'bench']
['feline', 'under', 'board']
['feline', 'under', 'table']
['cat', 'below', 'bench']
['cat', 'below', 'board']
['cat', 'below', 'table']
['cat', 'down', 'bench']
['cat', 'down', 'board']
['cat', 'down', 'table']
['cat', 'beneath', 'bench']
['cat', 'beneath', 'board']
['cat', 'beneath', 'table']
['cat', 'under', 'bench']
['cat', 'under', 'board']
['cat', 'under', 'table']

Upvotes: 1

Related Questions