I think Prasad needs to think carefully about his problem, IF it requires all such sequences.
Lets look at a much smaller problem, for only 16 bit sequences. Assume that each constant subsequence is at least 4 bits long. The first subsequence may be composed of zeros, or ones, so clearly WLOG we can find all sequences where the first subsequence is composed of zeros.
Thus, if we have the sequence 0000111100001111, there is a mirrored sequence 1111000011110000 that corresponds to it. So we need only find those that start with zeros, then we can mirror them all at once.
A good way to think of the problem is NOT in terms of sequences of bits, but in terms of where the transitions occur. There are fewer transitions than bits, so this reduces the problem complexity a little.
Next, those transitions can be viewed as integer partitions of 16, where no element in the partition is less than 4 (assuming the minimum sub-sequence length is 4.) That is, we can write
which would correspond to the sequence of bits
(Think about how this correspondence works, and why it is a simplification of the problem.)
Of course, that sequence does not satisfy the minimum length subsequence requirement. Using my partitions function (found on the file exchange)
partitions(16,4:16)
ans =
4 0 0 0 0 0 0 0 0 0 0 0 0
0 2 1 0 0 0 0 0 0 0 0 0 0
1 0 2 0 0 0 0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0 0 0 0
2 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1
Thus, the first row says we can write
thus as 4 fours. That implies the 16 bit sequence 0000111100001111, which except for its mirror, is the only on of that exact type. The second row tells us it can also be written as
Of course, there are 3 ways to permute those numbers, so we also have
16 = 5 + 6 + 5
16 = 6 + 5 + 5
Each of those permuted partitions corresponds to a unique 16 bit sequence, so we would have
0000000000111111
0000011111100000
0000001111100000
and then the mirror image of each of those sequences.
It is now fairly simple to generate all such 16 bit sequences from the call to partitions above. To do the same thing for 48 bit sequences will take a large amount of memory though, and MUCH CPU time, even with the tricks I have shown here.
Best Answer