[Solved]: How does one efficiently produce all binary sequences with an equal number of 0’s and 1’s?

ignougroup
Problem Detail: 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.

Asked By : Vidit Nanda

Answered By : tranisstor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12992