CODEWITHSUNDEEP
python
HighwayJohn
HighwayJohn

Reputation: 921

replace characters in a list of strings and create all possibilities

Hey I encountered a new problem in my code. At one point I have a list which does look like this one. (Usually much longer but this is not import to understand the problem)

['-0---11-', '--1--110', '01---100', '1--101-0', '10-1-1-0']

At positions with a bar can either be a 0 or a 1. Now I want to know for example how many unique strings with only 3 bars left does the list represent. In the example above the last three strings already only have three bars but the first two strings have four and five bars. '-0---11-'can thus represent '-0--1111','-0--1110','000--11-',.... So my idea is basically first to create all possibilities and then search for unique ones, so that I dont overcount. My question is now how I can create all possibilities?

Edit: An other more simple example which perhaps clarify my problem. Let's say the list does look like:

['--11', '--10', '010-']

Now I want to see how many unique strings I have when I only have at max 1 bar. Each bar represents a 1 or 0 so I have to write down all possibilities. The result would be:

['-111', '-011', '0-11', '1-11',  '-010', '-110', '0-10', '1-10',   '010-']

I hope I didn't forget any possibility. Now I have to search for duplicates and want to delete them. In this example there aren't any so I am done.

Upvotes: 3

Views: 134

Answers (1)

Brendan Abel
Brendan Abel

Reputation: 37549

You could use a recursive solution like this

def possibilities(pattern, ndash=0):
    if ndash <= pattern.count('-'):
        if not pattern:
            yield ''
        else:
            if pattern[0] == '-' and ndash > 0:
                for subpattern in possibilities(pattern[1:], ndash - 1):
                    yield '-' + subpattern
            for subpattern in possibilities(pattern[1:], ndash):
                if pattern[0] in '0-':
                    yield '0' + subpattern
                if pattern[0] in '1-':
                    yield '1' + subpattern

This is a generator function, so in order to get values from it, you need to iterate over the generator.

>>> gen = possibilities('1----0', 3)
>>> for s in gen:
...     print s

Or you can just feed it to list to get a list of all possibilities.

>>> from pprint import pprint
>>> pprint(list(possibilities('1----0', 3)
['1---00',
 '1---10',
 '1--0-0',
 '1--1-0',
 '1-0--0',
 '1-1--0',
 '10---0',
 '11---0']

Upvotes: 1

Related Questions