[FIXED] How to create all possible phrases from two lists, with a few conditions to follow

Issue

I have two lists alt, runs (a pair). they always have the same size.

the items inside alt are going to be a random combination of the following five options: "verb", "article", "constant", "o-constant", "variable"

the items of runs are always different from one pair to another

here is an example:

alt = ["constant", "variable", "constant", "o-constant"]
runs = ["fix", "something", "for", "a meal"]

what I want to achieve, is to generate all possible sentences for each pair.

but there are a few rules to follow:

1. "constant": should always be there in every possible outcome
2. "variable": should be ignored - should not appear in any possible outcome

example#1:

alt = ["constant", "variable", "constant", "variable"]
runs = ["abduct", "someone", "from", "someone or something"]

desired_outcome= ["abduct from"]

example#2:

alt = ["constant", "variable"],
runs = ["able to", "do something"]

desired_outcome= ["able to"]

3. if there is more than one "constant", all of them should always be there in every possible outcome

example:

alt = ["constant", "variable", "o-constant", "constant", "variable"]
runs = ["zoom", "someone or something", "over", "to", "someone"]
desired_outcome = ["zoom to", "zoom over to"]

4. "article" and "o-constant": should be in one version of each possible outcome

example#1:

alt = ["article", "constant"]
runs = ["an", "absent-minded professor"]

desired_outcome= ["an absent-minded professor", "absent-minded professor"]

example#2:

alt = ["constant", "o-constant", "constant", "variable"]
runs = ["abut", "up", "against", "something"]

desired_outcome= ["abut against", "abut up against"]

example#3:

alt = ["article", "o-constant", "constant"],
runs = ["a", "damn", "sight better"],

desired_outcome= ["a damn sight better", "a sight better", "damn sight better", "sight better"]

5. "verb": each verb can appear once in a possible outcome

example#1:

alt = ["verb", "verb", "constant"]
runs = ["from", "since", "day one"]

desired_outcome= ["from day one", "since day one", "day one"]

example#2:

alt = ["verb", "verb", "verb", "article", "constant", "o-constant", "variable"]
runs = ["get", "have", "give", "a"      , "free hand", "with"     , "someone or something"]

desired_outcome=  ["a free hand with", "a free hand", "free hand", "free hand with",
"get a free hand with", "get free hand with", "get a free hand", "get free hand",
"have a free hand with", "have free hand with", "have a free hand", "have free hand",
"give a free hand with", "give free hand with", "give a free hand", "give free hand"]

6. since I'm trying to create English phrases, the order of the items in the 'runs' list should be considered and kept the same when generating possibilities.

Those two lists come in different lengths and random patterns. I'm not sure how to approach this problem.

Solution

The idea is to start with what is certainly going to be in the output: the constants. And then add the articles/o-constants followed by the verbs according to their specific (slightly different) rule sets. In the end, we sort the list according to the order in the input.

It's probably possible to optimize the code tremendously, but I figured your question was more a conceptual one than a performance-based one. A good first step would be to combine the logic of the articles and the verbs, as it is very similar. But I'll leave that up to you :)

def combs(items):
    if len(items) == 0:
        return [[]]
    cs = []
    for c in combs(items[1:]):
        cs += [c, c+[items[0]]]
    return cs

alts = ["verb", "verb", "verb", "article", "constant", "o-constant", "variable"]
runs = ["get", "have", "give", "a", "free hand", "with", "someone or something"]

# calculate the possible outcomes, starting with the constants
output = [[run for alt, run in zip(alts, runs) if alt == 'constant']]

# deal with the articles (+ o-constants)
articles = [run for alt, run in zip(alts, runs) if alt == 'article' or alt == 'o-constant']
# calculate all possible combinations of articles (+ o-constants)
poss_articles = [comb for comb in combs(articles)]
if len(poss_articles) > 1:
    new_output = output.copy()
    for out in output:
        for articles in poss_articles[1:]:
            new_output.append(out + articles)
    output = new_output

# deal with the verbs
verbs= [run for alt, run in zip(alts, runs) if alt == 'verb']
if len(verbs) > 0:
    new_output = output.copy()
    for out in output:
        for verb in verbs:
            new_output.append(out + [verb])
    output = new_output

# get the correct ordering
final_output = []
for out in output:
    final_output.append(" ".join([word for word in runs if word in out]))

Answered By - Tim J