1

I have an issue where I have two options for each character in a n-char long string like so:

options1 = ['0','0','0','0']
options2 = ['1','1','1','1']

For simplicity I have used only '0' or '1' as options in this example and the string is only 4 characters long, but in my real problem the characters of the options are completely unique to the slot they belong in, and the strings can vary in size. How do I enumerate all possible versions of that string? i.e. I want the following output:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1111
Sillydan
  • 104
  • 13
  • maybe you are looking for `itertools.product`; generate all possible product of two lists – user13966865 Dec 06 '20 at 18:44
  • I tried that, but that gives me the cartesian product (all combinations of pairs of elements), which I dont want. – Sillydan Dec 06 '20 at 18:50
  • 1
    @Sillydan: It will work, you just need to transpose the inputs: `itertools.product(*zip(options1, options2))`. – ShadowRanger Dec 06 '20 at 18:51
  • Looks like you can also use a python tool: itertools https://stackoverflow.com/questions/7074051/what-is-the-best-way-to-generate-all-possible-three-letter-strings – Lizzo Dec 06 '20 at 18:53

2 Answers2

3

Use zip to transpose and itertools.product to select across each pair of options:

from itertools import product

for x in map(''.join, product(*zip(options1, options2))):
    print(x)

map(''.join, ...) isn't needed if you're okay with getting back tuples of the selection, but it makes it faster and more convenient if you want it converted back to strings anyway.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
1

This isn't something a little bfs couldn't handle:

def bfs(*options):
    strings = []
    frontier = [('',0)]
    while frontier:
        curr, idx = frontier.pop(0)
        if idx >= len(options[0]):
            strings.append(curr)
        else:
            for l in options:
                frontier.append((curr + l[idx], idx + 1))
    return strings

res = bfs(['0', '0', '0', '0'], ['1', '1', '1', '1'])
print(res)

Essentially, bfs makes a choice at each index, choose from a, or choose from b. This in turn picks up every possible route:

# res:
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

This has the nice option of working with more than just two arrays

M Z
  • 4,571
  • 2
  • 13
  • 27
  • 1
    I am accepting this answer over the other ones, since this is a general solution that can be used in other languages as well. For python specifically, it makes more sense to use itertools (like other people have suggested) – Sillydan Dec 06 '20 at 19:00
  • 1
    Minor improvement: Remove `strings = []` and `return strings`, and replace `strings.append(curr)` with `yield curr`. This makes the function a generator function that produces values lazily without forcing you to run to completion before processing the first output. When you want a `list`, you just wrap the call in the `list()` constructor, otherwise you can iterate it lazily without needing to store the complete results (that said, `frontier` will peak at the same size as the `list` you avoided, so the savings are not big-O relevant). – ShadowRanger Nov 18 '21 at 15:55