CODEWITHSUNDEEP
pythonnestedlogical-operatorspython-itertools
eljobso
eljobso

Reputation: 362

Calculating all combinations of nested lists based on logical expression

Let's assume I have a action list, which can contain three different type of actions:

Type A: can contain all types of actions (disjunction)
Type B: can contain all types of actions (ordered conjunction)
Type C: cannot contain subactions. This is the level I want to have at the end.

I thought about (based on: python - representing boolean expressions with lists) that the disjunction and conjunction could be represented by a tuple respectively a list, but I am not sure whether this is an optimal solution.

For type A and B, there is a dict which contains the type elements, e.g.

type_a = {
‘a1’: ('b1', 'a2'),
‘a2’: ('c1', 'c2')
}

type_b = {
‘b1’: ['c4', 'c5', 'c7'],
‘b2’:['c3', 'c4']
}

Detailed explanation:

‘a1’ is equal to ('b1', 'a2'), which is equal to (['c4', 'c5','c7'], 'c1', 'c2')

‘a2’ is equal to ('c1', 'c2')

‘b1’ is equal to ['c4', 'c5', 'c7']

‘b2’ is equal to ['c3', 'c4']

Example Input:

['a1', 'b2', 'c6']

Expected output:

The results should only contain type C actions.

raw

[(['c4', 'c5', 'c7'], 'c1', 'c2'), 'c3', 'c4', 'c6']

all combinations

['c4', 'c5','c7', 'c3', 'c4', 'c6']

['c1', 'c3', 'c4', 'c6']

['c2', 'c3', 'c4', 'c6']

Questions:

Thanks for any help.

Upvotes: 1

Views: 219

Answers (2)

Aran-Fey
Aran-Fey

Reputation: 43146

Sadly, itertools isn't of much help here. The following recursive beast seems to do the job however:

def combinations(actions):
    if len(actions)==1:
        action= actions[0]
        try:
            actions= type_a[action]
        except KeyError:
            try:
                actions= type_b[action]
            except KeyError:
                #action is of type C, the only possible combination is itself
                yield actions
            else:
                #action is of type B (conjunction), combine all the actions
                for combination in combinations(actions):
                    yield combination
        else:
            #action is of type A (disjunction), generate combinations for each action
            for action in actions:
                for combination in combinations([action]):
                    yield combination
    else:
        #generate combinations for the first action in the list
        #and combine them with the combinations for the rest of the list
        action= actions[0]
        for combination in combinations(actions[1:]):
            for combo in combinations([action]):
                yield combo + combination

The idea is to generate all possible values for the first action ('a1') and combine them with the (recursively generated) combinations of the remaining actions (['b2', 'c6']).

This also eliminates the need to represent conjunction and disjunction with lists and tuples, which, to be honest, I found rather confusing.

Upvotes: 1

janbrohl
janbrohl

Reputation: 2656

There is also a set type in Python which support set operations - if you do not care about ordering.

Upvotes: 0

Related Questions