How to iterate over vectors in order of probability in small space Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$.  For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent.  Using these probabilities, is there an efficient way to iterate over binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties) using space sublinear in the output size?  

Take for example $p = \{0.8, 0.3, 0.6\}$. The most likely vector is $(1,0,1)$ and the least likely is $\{0,1,0\}$.  

For very small $n$ we could label each of the $2^n$ vectors with its probability and simply sort but this would of course still not use sublinear space.

A close variant of this question was previously asked at https://cs.stackexchange.com/questions/24123/how-to-iterate-over-vectors-in-order-of-probability .
The following gives an algorithm that uses approximately $2^n$ time and $2^{n/2}$ space.

First, let's look at the problem of sorting the sums of all subsets of $n$ items.

Consider this subproblem: you have two sorted lists of length $m$, and you would like to create a sorted list of the pairwise sums of the numbers in the lists. You would like to do this in roughly $O(m^2)$ time (the output size), but sublinear space. We can achieve $O(m)$ space. We keep a priority queue, and pull the sums out of the priority queue in increasing order. 

Let the lists be $a_1 \ldots a_m$ and $b_1 \ldots b_m$, sorted in increasing order. We take the $m$ sums $a_i + b_1$, $i = 1 \ldots m$, and put them in a priority queue.

Now, when we pull the smallest remaining sum $a_i + b_j$ out of the priority queue, if $j &lt; m$ we then put the sum $a_i + b_{j+1}$ into the priority queue. The space is dominated by the priority queue, which always contains at most $m$ sums. And the time is $O(m^2 \log m)$, since we use $O(\log m)$ for each priority queue operation. This shows we can do the subproblem in $O(m^2 \log m)$ time and $O(m)$ space.

Now, to sort the sums of all subsets of $n$ numbers, we just use this subroutine where the list $a_i$ is the set of sums of subsets of the first half of the items, and the list $b_i$ is the set of sums of subsets of the second half of the items. We can find these lists recursively with the same algorithm.

We will now consider the original problem.  Let $S_0$ be the set of coordinates which are $0$, and $S_1$ be the set of coordinates which are $1$. Then
\begin{eqnarray*}\prod_{i \in S_0} p(v_i=0) \prod_{i \in S_1} p(v_i=1) &amp;=&amp; \prod_{1\leq i \leq n} p(v_i=0)   \prod_{i \in S_1} \frac{p(v_i=1)}{p(v_i=0)} \\ &amp;=&amp; \prod_{1\leq i \leq n} p(v_i=0) \exp\,\left(\sum_{i \in S_1} \log \frac{p(v_i=1)}{p(v_i = 0)}\right).\end{eqnarray*}

Sorting these numbers is the same as sorting the numbers $\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$, so we have reduced the problem to sorting the sums of subsets of $n$ items.