How to Generate Array of mimimum consecutive bits (1's or 0's)

As a part of my Project. I would like to generate all possible combinations of 48 bit binary sequence with minimum consecutive bits. for eg : if min consecutive bits is 4, then it should generate all combinations of 48 bit binary sequences with consecutive 0's or 1's should be greater than 4. eg: 00000111100000...... etc or 11110000011111100000.....and so on. I tried different methods using normal Loop operations but its takes infinitely long time (counting 1's or 0's from 2^0 to 2^48). is there any function which i could use to implement this idea. It would be really helpful. Thanks a lot.

[Vitali Avagyan]

Try to use nchoosk(n,k)! http://www.mathworks.co.uk/help/matlab/ref/nchoosek.html

[John D'Errico]

Vitali - No need to bother with nchoosek. 2^48 is wildly beyond anything you can generate.

[Vitali Avagyan]

John, thanks for the comment. The problem can be reduced to even less than 2^12 if the min consecutive bits are 4, hence nchoosek can be applied. I found some subcombinations for different min bits, however finding all the combinations requires an extra skill. If there is any other way, let me know.

[John D'Errico]

Prasad - you need to think carefully about the problem. There are an IMMENSE number of sequences for such a goal in 48 bits.

[Prasad]

Thank you Vitali and John for the reply. Yes I know it is really complex since there are many combination possible. My idea was to make a combination of different 4 bit sets, where I use a set which are likely to meet our requirement. eg - A - '0000', B-'0001', C -'0011' , D - '0111', E -'1111', F-'1000', G-'1100', H-'1110', I - '1111'. I tried in MATLAB to generate combination of these sets like 'AAAAAAAAAAAA' 'AAAAAAAAAAAB' 'AAAAAAAAAAAC' ...etc and so on. But when I run such a script, I getting out of memory error message. is there any way to implement this idea?

By this way I could filter atleast some sets of combinatins which will never occur like '1011' , '0100', '0110', '1001', '1101', '0010'.

Answer 1

[John D'Errico]

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

16 = 2 + 3 + 4 + 5 + 2

which would correspond to the sequence of bits

0011100001111100

(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

16 = 4 + 4 + 4 + 4

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

16 = 5 + 5 + 6

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.

[Prasad]

Thanks a lot John. I am goona try this definitely. Thanks again.

Answer 2

[Guillaume]

Have you calculated how many of such combinations there are? There may be too many to generate anyway.

If you limit it runs of multiple of 4 bits (i.e runs of 0,4,8,12,16,20,24,28,32,36,40 or 48 consecutive 1s and 0s), that's still 2^12 numbers = 4096. You can generate these with:

runs = {'0000', '1111'}; %the two bit patterns allowed
runcombinations = dec2bin(0:2^12-1, 12) - '0'; %generate all combinations, where 0 = run of 4 '0' and 1 is run of 4 '1';
nibbles48bit = runs(runcombinations + 1); %replace 0 with '0000' and 1 with '1111'
%the next two lines join the cell array columns together, couldn't find a more efficient way
temp = num2cell(nibbles48bit, 1);
combination48bit = strcat(temp{:});

[Prasad]

Thank you Guillaume for the reply. Yes there are too many combinations possible. This was my initial idea to reduce it by 12 x 4bits. I have tried this way but the problem is that it doesn't include the combimations of 5 or more. eg 00001111100000....etc. Hence it includes only combinations with multiples of 4.