Generating specific bit sequences in Python

Question

I have a list of numbers that represent the number of 1s in a row and I have an integer that represents the length of the entire sequence. So for example, if I get list [1, 2, 3] and length 8, then the only possible bit sequence is 10110111. But if the length was 9, I should get 010110111, 100110111, 101100111 and 101101110. I wonder if there is a simply pythonic way of doing this. My current method is

def genSeq(seq, length):
    strSeq = [str(i) for i in seq]
    strRep = strSeq + ["x" for i in xrange(length-sum(seq))]

    perm = list(set(permutations(strRep)))
    legalSeq = [seq for seq in perm if isLegal(seq) and [char for char in seq if char.isdigit()] == strSeq]
    return [''.join(["1"*int(i) if i.isdigit() else "0" for i in seq]) for seq in legalSeq]


def isLegal(seq):
    for i in xrange(len(seq)-1):
        if seq[i].isdigit() and seq[i+1].isdigit(): return False
    return True

print genSeq([1, 2, 3], 9)

I was thinking more along the lines if there is a standard way of doing this, from what I can understand, groupby would still require me to generate all bit sequences and then just filter them? If so, that is basically what my code already does. — Limon, Oct 15 '14 at 14:17
You can improve by doing it more iteratively, not building the whole list then filtering it; use `itertools.ifilter`, for example. — jonrsharpe, Oct 15 '14 at 14:24

score 1 · Accepted Answer · edited May 23 '17 at 10:25

My approach is as follows:

Figure out how many zeros will appear in the result sequences, by doing the appropriate arithmetic. We'll call this value n, and call the length of the input list k.
Now, imagine that we write out the n zeros for a given result sequence in a row. To create a valid sequence, we need to choose k places where we'll insert the appropriate number of ones, and we have n + 1 choices of where to do so - in between any two digits, or at the beginning or end. So we can use itertools.combinations to give us all the possible position-groups, asking it to choose k values from 0 up to n, inclusive.
Given a combination of ones-positions, in ascending order, we can figure out how many zeroes appear before the first group of ones (it's the first value from the combination), the second (it's the difference between the first two values from the combination), etc. As we iterate, we need to alternate between groups of zeros (the first and/or last of these might be empty) and groups of ones; so there is one more group of zeros than of ones, in general - but we can clean that up by adding a "dummy" zero-length group of ones to the end. We also need to get "overlapping" differences from the ones-positions; fortunately there's a trick for this.

This part is tricky when put all together; I'll write a helper function for it, first:

def make_sequence(one_positions, zero_count, one_group_sizes):
    zero_group_sizes = [
        end - begin
        for begin, end in zip((0,) + one_positions, one_positions + (zero_count,))
    ]
    return ''.join(
        '0' * z + '1' * o
        for z, o in zip(zero_group_sizes, one_group_sizes + [0])
    )

Now we can get back to the iteration over all possible sequences:

def generate_sequences(one_group_sizes, length):
    zero_count = length - sum(one_group_sizes)
    for one_positions in itertools.combinations(
        range(zero_count + 1), len(one_group_sizes)
    ):
        yield make_sequence(one_positions, zero_count, one_group_sizes)

Which we could of course then fold back into a single function, but maybe you'll agree with me that it's better to keep something this clever in more manageable pieces :)

This is more fragile than I'd like - the one_positions and one_group_sizes sequences need to be "padded" to make things work, which in turn requires assuming their type. one_positions will be a tuple because that's what itertools.combinations produces, but I've hard-coded the assumption that the user-supplied one_group_sizes will be a list. There are ways around that but I'm a little exhausted at the moment :)

Anyway, the test:

>>> list(generate_sequences([1,2,3], 9))
['101101110', '101100111', '100110111', '010110111']

>>> list(generate_sequences([1,1,1], 9))
['101010000', '101001000', '101000100', '101000010', '101000001', '100101000', '
100100100', '100100010', '100100001', '100010100', '100010010', '100010001', '10
0001010', '100001001', '100000101', '010101000', '010100100', '010100010', '0101
00001', '010010100', '010010010', '010010001', '010001010', '010001001', '010000
101', '001010100', '001010010', '001010001', '001001010', '001001001', '00100010
1', '000101010', '000101001', '000100101', '000010101']

Generating specific bit sequences in Python

1 Answers1