0
$\begingroup$

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one

Eg. suppose $n=4$, so the total number of the binary sequence is $2^{4}=16$. And the binary sequences are as follows $0000, 0001, 0010, 0011, 0100, 0101,0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$

Furthermore, let us consider $P\geq3$. Therefore we will select the flowing sequences only

$0000, 0001, 1000$.

Here, the problem is with the value of $n$, if it is large enough, such as $ n\geq100$ and $P\geq 10$. Then how to evaluate all the binary sequences, generated from $2^{100}$ for finding $P\geq 10$?

Currently, I am clueless about solving this issue and looking for an opinion or any thoughts or techniques from you. Please help, if possible.

$\endgroup$
5
  • $\begingroup$ Do the zeros have to be consecutive? $\endgroup$
    – Guy Coder
    Jan 19, 2022 at 10:21
  • $\begingroup$ There are no restrictions on the consecutiveness of zeros in a sequence. $\endgroup$
    – A Paul
    Jan 19, 2022 at 12:59
  • 2
    $\begingroup$ The output will be exponential in $n$, assuming that $P$ is small enough (i.e, not extremely close to being what $n$ is). So any algorithm you come up with, will probably not really be practical. What do you intend to use this algorithm for? If you know something else about the underlying problem you are trying to solve - it might allow to reduce the total number of binary strings you have to consider $\endgroup$
    – nir shahar
    Jan 19, 2022 at 13:23
  • $\begingroup$ I am also thinking about it. However, I posted it here with the hope that maybe there will be an extraordinary approach from someone. $\endgroup$
    – A Paul
    Jan 19, 2022 at 18:59
  • 1
    $\begingroup$ There are 2¹⁰⁰ binary sequences of length 100, and it's clear that most of them have at least 10 zeros. Indeed, more than half of them have at least 50 zeros. No algorithm, regardless how clever, will let you enumerate that many objects, not even if you had a million CPUs. So either that is not your real problem or your real problem has no solution. $\endgroup$
    – rici
    Jan 19, 2022 at 20:50

1 Answer 1

1
$\begingroup$

Let f(n, p) be the number of binary sequences with exactly P zeroes. You just calculate them in the right order and store the results:

f(n, 0) = 1 for all n. 
f(n, p) = 0 for all p > n. 
f(n, p) = f(n-1, p-1) + f(n-1, p) for 1 <= p <= n. 

Then you add the values f(n,p) for p >= P to get the number of sequences. Enumerating them is obviously impossible even if n is not very large.

$\endgroup$

Your Answer

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