10
$\begingroup$

A binary sequence of length $n$ is just an ordered sequence $x_1,\ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary tree structure in the following way: the root is "empty", but each left child corresponds to the addition of $0$ to the existing string and each right child to a $1$. Now, each binary sequence is simply a path of length $n+1$ starting at the root and terminating at a leaf.

Here's my question:

Can we do better if we only want to generate all binary strings of length $2n$ which have precisely $n$ zeros and $n$ ones?

By "can we do better", I mean we should have lower complexity than the silly algorithm which first builds the entire tree above and then tries to find those paths with an equal number of "left" and "right" edges.

$\endgroup$
  • $\begingroup$ Can you find a way to efficiently generate all strictly increasing sequences of $n$ numbers in the range from 1 to $2n$? $\endgroup$ – Cornelius Brand Jun 30 '13 at 14:31
  • $\begingroup$ I cannot comment on complexity, but my naive algorithm would generate the walks along the edges of a square grid from one corner to a diagonal one, using kind of backtrack scheme. That means that 01 and 10 end up in the same position (unlike your tree) but with backtrack we know this history. $\endgroup$ – Hendrik Jan Jun 30 '13 at 21:14
  • $\begingroup$ On a possibly different note, here is a Java implementation of an ${n \choose k}$-iterator. $\endgroup$ – Pål GD Jul 1 '13 at 9:26
6
$\begingroup$

Obviously there are $4^{n}$ binary strings of length $2n$. To traverse the binary an algorithm has to visit each node once, i. e. it has to do $$ \sum_{i=0}^{2n} 2^i = 2^{2n+1} - 1 = \mathcal{O}(4^n)$$ steps.

Let's consider a recursive algorithm which traverses the tree you described, but counts the number of ones and zeros on its way, i. e. it will only traverse the good part of the tree.
But how many such binary strings with $n$ 0's and $n$ 1's are there? We choose $n$ 1's for our strings of length $2n$ and use Stirling's formula in step 2: $$ {2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{4^n}{\sqrt{\pi n}} (1 + \mathcal{O}(1/n))$$

EDIT
Thanks to Peter Shor's comments we can also analyse the number of steps needed by the second algorithm, which counts the 1's and 0's. I'm citing his comment from below:

We want to find all binary sequences with exactly $n$ 0's and $n$ 1's. We traverse the binary tree where each node is a sequence of at most $2n$ 0's and 1's. We don't need to visit any node with more than $n$ 0's or more than $n$ 1's. how many nodes do we need to visit? There are ${i+j \choose i}$ strings with $i$ 0's and $j$ 1's. Summing this over all $i,j \leq n$ gives $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} − 1$. Now, we need to visit each of these nodes at a constant average cost per node. We can do this by visiting each left child first, and each right child second.

Using Stirling's formula again we obtain $$ {2n + 2 \choose n + 1} - 1 = 4^{n+1} \frac{1}{\sqrt{n+1}} (1 + \mathcal{O}(1/n)) - 1 = \mathcal{O}(\frac{4^n}{\sqrt{n}}) $$ as the running time of the new algorithm.

$\endgroup$
  • $\begingroup$ You have to be a bit more careful. Presumably after generating each string, we process it in $\Omega(n)$ time. So just processing all balanced strings takes time $\Omega(4^n \sqrt{n})$. If the optimized "silly" generation algorithm is indeed $O(4^n)$, then there's nothing much to be gained by switching to a smarter algorithm, other than opportunities for bugs. $\endgroup$ – Yuval Filmus Jun 30 '13 at 15:46
  • $\begingroup$ @Yuval Filmus: What exactly do you mean be "string processing"? If you mean the time spent on the output, which is certainly $\Theta(n)$, then you have to consider that factor also in the running time of the "silly" algorithm, which then is $O(4^n n)$. $\endgroup$ – tranisstor Jun 30 '13 at 16:11
  • 2
    $\begingroup$ My point was that if you're concerned with the difference between $4^n$ and $4^n/\sqrt{n}$, then as a minimum you have to state the correct running times; $\tilde{O}(4^n)$ isn't enough to reveal any potential difference between the two algorithms. In addition, you have to be careful analyzing your proposed new algorithm, to see that these "negligible" small factors do not make it slower than the trivial algorithm. $\endgroup$ – Yuval Filmus Jun 30 '13 at 17:05
  • 2
    $\begingroup$ How do you only build the "good part" of the tree without having to include the "bad parts" as well? You need to include all nodes of the tree which do not have more than $n$ left children or $n$ right children on the path from the root to them. This works, but you need an additional argument to show that it works. Specifically, you need to use the formula $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} -1$. $\endgroup$ – Peter Shor Jun 30 '13 at 17:36
  • 2
    $\begingroup$ We want to find all binary sequences with exactly $n$ 0's and $n$ 1's. We traverse the binary tree where each node is a sequence of at most $2n$ 0's and 1's. We don't need to visit any node with more than $n$ 0's or more than $n$ 1's. how many nodes do we need to visit? There are $i+j \choose i$ strings with $i$ 0's and $j$ 1's. Summing this over all $i,j \leq n$ gives $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i}={2n+2 \choose n+1}-1$. Now, we need to visit each of these nodes at a constant average cost per node. We can do this by visiting each left child first, and each right child second. $\endgroup$ – Peter Shor Jun 30 '13 at 22:44
2
$\begingroup$

Perhaps I'm being thick, but the original question asked for a way to generate all "balanced" binary sequences of length 2n that was more efficient than traversing a tree of all binary sequences of length 2n and outputting only those which were balanced. So why use a tree at all?

Here's pseudocode for a recursive algorithm that generates all such sequences (the keyword "yield" sends a sequence to the output):

function all-balanced(n) {
  all-specified( "", n, n );
};

function all-specified( currentString, zeroes, ones ) {

  if (zeroes == 0) {
    for i = 0 to ones {
      currentString += "1";
    };
    yield currentString;
    return;
  };

  if (ones == 0) {
    for i = 0 to zeroes {
      currentString += "0";
    };
    yield currentString;
    return;
  };

  all-specified( currentString+"0", zeroes-1, ones );
  all-specified( currentString+"1", zeroes, ones-1 );
  return;
};

If I'm misunderstanding something, please tell me, but it seems to me that this is about the most efficient answer to the problem actually posed, which never specified the use of a tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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