Styjun

Given a list of strings, I want to return all possible permutations where the strings may contain an OR operator.

How can I do this? A pointer to which functions I should use is ok (with code will be helpful, but not required).

For example,

#!/usr/bin/env python3
import itertools

list_of_strings = ['a|b', 'c']

# I probably need to add some '|' splitter here

for permutation in itertools.permutations(list_of_strings, 2):
 print(''.join(str(word) for word in permutation))

prints

a|bc
ca|b

but I want

ac
bc
ca
cb

That is, using either 'a' or 'b', but not both.

There may be multiple strings strings with '|'. For example, list_of_strings = ['a|b', 'c', 'd|e'].

There may be multiple ORs within a string. For example, list_of_strings = ['a|b|d|e', 'c'].

The previous example should print

ac
bc
dc
ec
ca
cb
cd
ce

The strings may be longer than one character. For example, list_of_strings = ['race', 'car|horse'].

The output should be

racecar
racehorse
carrace
horserace

There are just a few steps.

1. Split each of your original strings on | to get lists of strings.


2. Compute the permutations of your list of lists of strings.


3. Compute the product of each permutation


4. Join each element of those products with the null string.

Using the itertools and operator modules, it looks like this:

>>> from itertools import product, permutations
>>> from operator import methodcaller
>>> splitter = methodcaller("split", "|")
>>> list_of_strings = ["a|b", "c", "foo|bar"]
>>> strings = ["".join(y) for x in permutations(map(splitter, list_of_strings)) for y in product(*x)]
>>> for s in strings:
... print(s)
...
acfoo
acbar
bcfoo
bcbar
afooc
abarc
bfooc
bbarc
cafoo
cabar
cbfoo
cbbar
cfooa
cfoob
cbara
cbarb
fooac
foobc
barac
barbc
fooca
foocb
barca
barcb

The long line more readably is

strings = ["".join(y) 
 for x in permutations(map(splitter, list_of_strings))
 for y in product(*x)]

If you are not as prone to using map as I usually am, you can get rid of methodcaller and use a generator expression for the argument to permutations.

strings = ["".join(z)
 for y in permutations(x.split("|") for x in list_of_strings)
 for z in product(*y)]

There is a solution with two stages:

1. generate permutations of list_of_strings




2. recursively parse or operators

Have a look, seems to pass all your test cases, feel free to ask clarification in comments.

import itertools


def permutations_with_ors(list_of_strings):
 for item in itertools.permutations(list_of_strings):
 yield from parse_ors(item)


def parse_ors(tuple_of_strings):
 for i, string in enumerate(tuple_of_strings):
 if '|' in string:
 for item in string.split('|'):
 replaced = (
 tuple_of_strings[:i] + 
 (item,) + 
 tuple_of_strings[i + 1:]
 )
 yield from parse_ors(replaced)
 break
 else:
 yield ''.join(tuple_of_strings)


list_of_strings = ['a|b', 'c']

for item in permutations_with_ors(list_of_strings):
 print(item)

# output:
# ac
# bc
# ca
# cb

print()

list_of_strings = ['a|b|d|e', 'c']

for item in permutations_with_ors(list_of_strings):
 print(item)

# output:
# ac
# bc
# dc
# ec
# ca
# cb
# cd
# ce

print()

list_of_strings = ['a|b', 'c', 'd|e']

for item in permutations_with_ors(list_of_strings):
 print(item)

# output is quite long, please check it yourself

print()

list_of_strings = ['race', 'car|horse']

for item in permutations_with_ors(list_of_strings):
 print(item)

# output:
# racecar
# racehorse
# carrace
# horserace