0

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

Seth McClaine
  • 9,142
  • 6
  • 38
  • 64
Linke
  • 1
  • 1
  • Please provide what you have so far so we can improve on your attempt – Seth McClaine Jun 05 '20 at 21:30
  • itertools.product? https://pypi.org/project/django-pwdtk/#history – gelonida Jun 05 '20 at 21:50
  • Does this answer your question? [How to apply itertools.product to elements of a list of lists?](https://stackoverflow.com/questions/3034014/how-to-apply-itertools-product-to-elements-of-a-list-of-lists) – RichieV Sep 29 '20 at 03:03

2 Answers2

1

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']
SeoHyeong Jeong
  • 11
  • 2
1

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
Mo...
  • 1,812
  • 2
  • 17
  • 22