CODEWITHSUNDEEP
pythoncombinationspermutationpython-itertools
horcle_buzz
horcle_buzz

Reputation: 2171

Generating all combinations of a list of strings with both parentheses and an operator being permuted, too

Let's say I have a list of the strings: l = ['A','B','C','D']

I know that to generate all combinations of these with replacement, choose n, that I would use the itertools.combinations library method to get them.

For example, list(combinations(l, 2)) would give me

[['A','B'], ['A','C'],['A','D'],['B','C'],['B','D'],['C','D']]

However, instead of brackets, I would like parentheses:

['(A,B)', '(A,C)','(A,D)','(B,C)','(B,D)','(C,D)']

Now, let's say I want to extend this and add in two operations for these AND and OR:

So that I would get ['(A','AND','B)', '(A','OR','B)',etc.]

Extend that even further, to get nested parentheses in the case where n=3:

['((A','AND','B)', 'AND', 'C)', '((A','AND','B)', 'OR', 'C)', '((A','OR','B)', 'OR', 'C)', '((A','OR','B)', 'AND', 'C)', etc.]

With it ideally being of the form:

['((A AND B) AND C)', '((A AND B) OR C)', '((A OR B) OR C)', '((A OR B) AND C)', etc.]

So, in summary, I am choosing combinations a list n elements at a time, with permutations on operators ['AND', 'OR'] and adding nesting from the left.

I've done something similar in JavaScript, but there it was easier, since the user would construct the actual sentence. It was not created from a set of permutations and combinations.

Upvotes: 3

Views: 458

Answers (2)

blhsing
blhsing

Reputation: 106936

You can use itertools.combinations to pick operands from the given list, use itertools.product to produce combinations of operators, and use itertools.product again to produce all mixes of operands and operators, and use a for loop that keeps nesting lists according to the chosen operands and operators to build the desired output:

from itertools import combinations, product
def expressions(l, n):
    for (operations, *operands), operators in product(
            combinations(l, n), product(('AND', 'OR'), repeat=n - 1)):
        for operation in zip(operators, operands):
            operations = [operations, *operation]
        yield operations

so that list(expressions(['A','B','C','D'], 3)) returns:

[[['A', 'AND', 'B'], 'AND', 'C'],
 [['A', 'AND', 'B'], 'OR', 'C'],
 [['A', 'OR', 'B'], 'AND', 'C'],
 [['A', 'OR', 'B'], 'OR', 'C'],
 [['A', 'AND', 'B'], 'AND', 'D'],
 [['A', 'AND', 'B'], 'OR', 'D'],
 [['A', 'OR', 'B'], 'AND', 'D'],
 [['A', 'OR', 'B'], 'OR', 'D'],
 [['A', 'AND', 'C'], 'AND', 'D'],
 [['A', 'AND', 'C'], 'OR', 'D'],
 [['A', 'OR', 'C'], 'AND', 'D'],
 [['A', 'OR', 'C'], 'OR', 'D'],
 [['B', 'AND', 'C'], 'AND', 'D'],
 [['B', 'AND', 'C'], 'OR', 'D'],
 [['B', 'OR', 'C'], 'AND', 'D'],
 [['B', 'OR', 'C'], 'OR', 'D']]

Upvotes: 2

Ajax1234
Ajax1234

Reputation: 71461

You can use recursion with a generator:

def op(d, n, _d, c = []):
  if _d == 1:
    yield c
  else:
    for i in d:
      if sum(isinstance(h, list) or h not in {'AND', 'OR'} for h in c) == n:
         yield from op(d, n, _d-1, c=[c, 'OR', i])
         yield from op(d, n, _d-1, c=[c, 'AND', i])
      else:
         if not c:
           yield from op(d, n, _d, c=[i])
         else:
           yield from op(d, n, _d, c=[*c, 'OR', i])
           yield from op(d, n, _d, c=[*c, 'AND', i])

result = list(op(['A','B','C','D'], 2, 2))

Output (first ten results):

[[['A', 'OR', 'A'], 'OR', 'A'], [['A', 'OR', 'A'], 'AND', 'A'], [['A', 'OR', 'A'], 'OR', 'B'], [['A', 'OR', 'A'], 'AND', 'B'], [['A', 'OR', 'A'], 'OR', 'C'], [['A', 'OR', 'A'], 'AND', 'C'], [['A', 'OR', 'A'], 'OR', 'D'], [['A', 'OR', 'A'], 'AND', 'D'], [['A', 'AND', 'A'], 'OR', 'A'], [['A', 'AND', 'A'], 'AND', 'A']]

This solution will enable you to control both the length and depth of each element in result. For instance, when generating to a depth of 4:

result = list(op(['A','B','C','D'], 2, 4))
print(result[:10])

Output:

[[[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'A'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'B'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'B'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'C'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'C'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'OR', 'D'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'OR', 'A'], 'AND', 'D'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'AND', 'A'], 'OR', 'A'], [[[['A', 'OR', 'A'], 'OR', 'A'], 'AND', 'A'], 'AND', 'A']]

Upvotes: 2

Related Questions