1
$\begingroup$

Lets take an example of the range of N=32 bits

2^32 = 4294967296

00000000000000000000000000000000
00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000011
...
11111111111111111111111111111100
11111111111111111111111111111101
11111111111111111111111111111110
11111111111111111111111111111111

Now lets consider a subset within this range whose consecutive 0s can be 0 to maximum 3 0s.

The following are examples of valid and invalid subsets -

Valid subset (consecutive 0s - 0 to maximum 3):

00100100100100100100100100100101 - (subset 0)
10101010101010101010101010101010 - (subset 1)
10010010010010001000100010101111 - (subset 2)
11011001000111101000100010010011 - (subset 3)
...
11111111111111111111111111111111 - (subset S max value)

So, count(valid subset) < 2^32

Invalid subset (at least 1 consecutive 0s > 3):

10000111111111111111111111111001
10101010100000000001111000100111
11111111101010101010101010000001
10000000000000001111010100010101
...

I have the following queries -

  1. How to find the total count of valid subsets for a given value of N (ex. 2^32, 2^40, 2^64 etc)
  2. How to dynamically generate the subset value for each matching subset, in an incremental manner, for a given value of N (ex. 2^32, 2^40, 2^64 etc)

So, for N=32,

If the value is "00100100100100100100100100100101", then subset value "0" must be dynamically generated
If the value is "10101010101010101010101010101010", then subset value "1" must be dynamically generated
If the value is "10010010010010001000100010101111", then subset value "2" must be dynamically generated
If the value is "11011001000111101000100010010011", then subset value "3" must be dynamically generated
If the value is "11111111111111111111111111111111", then subset value "subset S max" must be dynamically generated
  1. Consecutively, given the subset value, the bit value must also be dynamically generated

So, for N=32,

If subset value is "0", then bit value "00100100100100100100100100100101" must be dynamically generated
If subset value is "subset S max", then bit value "11111111111111111111111111111111" must be dynamically generated

and so on...

The main point is dynamically generating the values, so they are not required to be stored; this is feasible for large values of N (ex. 2^32, 2^40, 2^64 etc and greater)

$\endgroup$
3

1 Answer 1

2
$\begingroup$

Let $A(n,k)$ denote the number of valid strings of length $n$ ending with a string of $k$ zeroes. Then:

  • $A(0,0) = 1$
  • $A(0,1) = A(0,2) = A(0,3) = 0$
  • $A(n+1,0) = A(n,0) + A(n,1) + A(n,2) + A(n,3)$
  • $A(n+1,k+1) = A(n,k)$

You are interested in $A(n,0) + A(n,1) + A(n,2) + A(n,3)$ for various values of $n$.

Using these formulas, it is routine to implement ranking and unranking, that is, to convert a valid string to its index in the list of all valid strings, ordered lexicographically (ranking) and vice versa (unranking).


With slightly more effort, we can obtain a direct recurrence formula for $B(n) = A(n,0) + A(n,1) + A(n,2) + A(n,3)$: $$ B(n) = B(n-1) + B(n-2) + B(n-3) + B(n-4) $$ with initial values $B(0),B(1),B(2),B(3) = 1,2,4,8$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.