<p>The following gives an algorithm that uses approximately $2^n$ time and $2^{n/2}$ space.</p>

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

<p>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. </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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*}</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-10T07:53:04.280Z
Is there plausibly a reduction which would make a poly time/space solution implausible?
Simd
CC BY-SA 3.0
2014-06-10T12:31:34.913Z
You're probably not going to get a solution which takes less than $2^n$ time, since that's the size of the output (and my solution takes $n\, 2^n$ time). I don't have a good lower bound for space, though.
Peter Shor 
CC BY-SA 3.0
2014-06-10T18:07:47.440Z
Thank you. I didn't mean poly time of course but rather something linearish in the output size and poly space.
Simd
CC BY-SA 3.0
2014-06-10T02:36:39.053Z
2014-06-10T03:40:00.083Z
2014-06-10T03:40:00.083Z
Peter Shor 
<p>We can do that in space $O(n)$ (if we don't care about the running time).</p>

<ol>
<li>For a given string $x \in \{0,1\}^n$, we can compute in space $O(n)$ the number $r(x)$ of strings that are more likely than $x$; that is, the number of $x'$ s.t. $p(x') &gt; p(x)$: just go over all $x'\in \{0,1\}^n$ and count the number of $x'$ s.t. $p(x') &gt; p(x)$. Note that $r(x)$ is the sequential number of string $x$ in the output.</li>
<li>For every $k$, we can find $x$ with $r(x) = k$ in space $O(n)$: go over all $x \in \{0,1\}^n$, for each $x$ compute $r(x)$, stop and output $x$ if $r(x) = k$.</li>
<li>Now just go over all $k$ from $0$ to $2^n-1$, for each $k$ print $x$ with $r(x) =k$.</li>
</ol>

<p>(We should also take care of possible ties, but this is not difficult.)</p>

CC BY-SA 3.0
2014-06-09T20:46:09.607Z
Thank you. That is quite a slow algorithm however :)
Simd
CC BY-SA 3.0
2014-06-09T19:55:18.753Z
2014-06-09T19:55:18.753Z
Yury
<p>Edit: This answer is incorrect. See comments for details. ~gandaliter</p>

<p>Linear in the output means $O(2^n)$. I think the obvious algorithm only uses $O(n)$ space, apart from the output itself of course.</p>

<ol>
<li><p>Take the list containing the pairs $(i, p_i)$, and sort it by $\left|0.5 - p_i\right|$, largest first.</p></li>
<li><p>Define a doubly recursive function which takes a list of such pairs and a partially filled vector $v$, sets the value of $v_i$ as $1$ if $p_i &gt; 0.5$, and $0$ otherwise, and recurses (using the tail of the list, and $v$), then flips $v_i$ and recurses again. If the list is empty it instead outputs $v$.</p></li>
<li><p>Call this recursive function on the sorted list and an empty vector.</p></li>
</ol>

<p>The intuition is that you are setting the values of the most certain elements in the vector first (the ones whose probabilities are closest to $0$ and $1$), and filling the vector in like that, finishing with the ones whose probabilities are closest to $0.5$. Each possible value that the whole vector could take is outputted in order of its probability.</p>

<p>The run time is $O(2^n)$, which is the lower bound because that is the length of the output. The space complexity is $O(n)$ because the sort doesn't require more than that, and the recursive length is the length of the vector, which is $n$. I believe this is also the lower bound because there must be a different state in memory for every time step in the running of the algorithm, and the time complexity is $O(2^n)$. $O(n)$ states in memory are required to enumerate $O(2^n)$ time steps. Therefore this algorithm is worst-case complexity optimal.</p>

CC BY-SA 3.0
2014-06-08T07:44:19.320Z
The other answer is certainly different as it requires a priority queue and hence uses $\Theta(2^n)$ space.
Simd
CC BY-SA 3.0
2014-06-08T11:04:33.690Z
Thanks. I clearly didn't read it carefully enough! I've edited my answer.
gandaliter
CC BY-SA 3.0
2014-06-08T13:16:01.003Z
Are you sure this solution works? I couldn't figure out the details of the double recursion (pseudocode would help!) but I don't see how this could work. In particular, your solution seems to be local: if it set $v_1=1$ it's now going to output $2^{n-1}$ answers with $v_1=1$. But the actual answers shouldn't look this way. In fact, as far as I understood your solution, it seems to fail even for the simplest case where all $p_i=0.5$.
greg
CC BY-SA 3.0
2014-06-09T11:28:50.160Z
You're right, this doesn't work. Sorry!
gandaliter
CC BY-SA 3.0
2014-06-07T22:39:45.833Z
2014-06-09T11:30:05.700Z
2014-06-09T11:30:05.700Z
gandaliter
<p>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?  </p>

<p>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\}$.  </p>

<p>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.</p>

<p>A close variant of this question was previously asked at <a href="https://cs.stackexchange.com/questions/24123/how-to-iterate-over-vectors-in-order-of-probability">https://cs.stackexchange.com/questions/24123/how-to-iterate-over-vectors-in-order-of-probability</a> .</p>

CC BY-SA 3.0
2014-06-07T19:37:33.893Z
Is there any reason you didn't ask the followup question there too ? Is the main issue here one of doing this in sublinear space ?
Suresh Venkat
CC BY-SA 3.0
2014-06-07T19:38:24.277Z
@SureshVenkat Yes the problem is entirely about sublinear space (in the output size). I asked it here as I think the question may be very hard.
Simd
CC BY-SA 3.0
2014-06-09T22:03:08.707Z
Solving this in $\textrm{poly}(n)$ space and time seems to require techniques similar to SUBSET-SUM (quickly knowing which sums of subsets nearly cancel different sums).  Thus, it is unlikely to have a fast solution.
Geoffrey Irving
CC BY-SA 3.0
2014-06-10T06:38:57.037Z
@GeoffreyIrving Do you think this intuition can be made more formal?
Simd
<ds.algorithms><space-bounded>
How to iterate over vectors in order of probability in small space
Simd
# How to iterate over vectors in order of probability in small space

(Asked by: username_0 on 2014-06-07)

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> .

**Tags:** ds.algorithms, space-bounded
> **Comments:**
> **username_1**: Is there any reason you didn't ask the followup question there too ? Is the main issue here one of doing this in sublinear space ?  
> **username_0**: @SureshVenkat Yes the problem is entirely about sublinear space (in the output size). I asked it here as I think the question may be very hard.  
> **username_2**: Solving this in $\textrm{poly}(n)$ space and time seems to require techniques similar to SUBSET-SUM (quickly knowing which sums of subsets nearly cancel different sums).  Thus, it is unlikely to have a fast solution.  
> **username_0**: @GeoffreyIrving Do you think this intuition can be made more formal?  

---

## 3 answers

### Answer by username_3 on 2014-06-10. Score: 8

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 < 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) &=& \prod\_{1\leq i \leq n} p(v\_i=0) \prod\_{i \in S\_1} \frac{p(v\_i=1)}{p(v\_i=0)} \\ &=& \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.

> **Comments:**
> **username_0**: Is there plausibly a reduction which would make a poly time/space solution implausible?  
> **username_3**: You're probably not going to get a solution which takes less than $2^n$ time, since that's the size of the output (and my solution takes $n\, 2^n$ time). I don't have a good lower bound for space, though.  
> **username_0**: Thank you. I didn't mean poly time of course but rather something linearish in the output size and poly space.  

---

### Answer by username_4 on 2014-06-09. Score: 4

We can do that in space $O(n)$ (if we don't care about the running time).

1. For a given string $x \in \{0,1\}^n$, we can compute in space $O(n)$ the number $r(x)$ of strings that are more likely than $x$; that is, the number of $x'$ s.t. $p(x') > p(x)$: just go over all $x'\in \{0,1\}^n$ and count the number of $x'$ s.t. $p(x') > p(x)$. Note that $r(x)$ is the sequential number of string $x$ in the output.
2. For every $k$, we can find $x$ with $r(x) = k$ in space $O(n)$: go over all $x \in \{0,1\}^n$, for each $x$ compute $r(x)$, stop and output $x$ if $r(x) = k$.
3. Now just go over all $k$ from $0$ to $2^n-1$, for each $k$ print $x$ with $r(x) =k$.

(We should also take care of possible ties, but this is not difficult.)

> **Comments:**
> **username_0**: Thank you. That is quite a slow algorithm however :)  

---

### Answer by username_5 on 2014-06-07. Score: 0

Edit: This answer is incorrect. See comments for details. ~gandaliter

Linear in the output means $O(2^n)$. I think the obvious algorithm only uses $O(n)$ space, apart from the output itself of course.

1. Take the list containing the pairs $(i, p\_i)$, and sort it by $\left|0.5 - p\_i\right|$, largest first.
2. Define a doubly recursive function which takes a list of such pairs and a partially filled vector $v$, sets the value of $v\_i$ as $1$ if $p\_i > 0.5$, and $0$ otherwise, and recurses (using the tail of the list, and $v$), then flips $v\_i$ and recurses again. If the list is empty it instead outputs $v$.
3. Call this recursive function on the sorted list and an empty vector.

The intuition is that you are setting the values of the most certain elements in the vector first (the ones whose probabilities are closest to $0$ and $1$), and filling the vector in like that, finishing with the ones whose probabilities are closest to $0.5$. Each possible value that the whole vector could take is outputted in order of its probability.

The run time is $O(2^n)$, which is the lower bound because that is the length of the output. The space complexity is $O(n)$ because the sort doesn't require more than that, and the recursive length is the length of the vector, which is $n$. I believe this is also the lower bound because there must be a different state in memory for every time step in the running of the algorithm, and the time complexity is $O(2^n)$. $O(n)$ states in memory are required to enumerate $O(2^n)$ time steps. Therefore this algorithm is worst-case complexity optimal.

> **Comments:**
> **username_0**: The other answer is certainly different as it requires a priority queue and hence uses $\Theta(2^n)$ space.  
> **username_5**: Thanks. I clearly didn't read it carefully enough! I've edited my answer.  
> **username_6**: Are you sure this solution works? I couldn't figure out the details of the double recursion (pseudocode would help!) but I don't see how this could work. In particular, your solution seems to be local: if it set $v_1=1$ it's now going to output $2^{n-1}$ answers with $v_1=1$. But the actual answers shouldn't look this way. In fact, as far as I understood your solution, it seems to fail even for the simplest case where all $p_i=0.5$.  
> **username_5**: You're right, this doesn't work. Sorry!  

---

