Number of possible sequence partitioning

Question

Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) so that any sub-sequence starts and ends with a 1, and can contain an arbitrary number of 0s?

For example: Given the sequence 1 0 1 1 0 1 there are only 3 ways of partitioning the sequence:

1.
1 0 1
      1 0 1

2.
1 0     0 1
    1 1

3.
1 0   1
    1   0 1

I am pretty sure the solution implies dynamic programming, since the solution requires a fast execution time (< 1 second).

Answer 1

The problem formulation is not entirely clear. This answer assumes that the allowed subsequences are of the form $10^*1$. Other variants can be solved in a similar way.

Suppose that the original sequence is $a_1,\ldots,a_n$. Let $b(i,x)$ denote the number of ways to partition $a_1,\ldots,a_i$ into any number of subsequences of the form $10^*1$ and $x$ subsequences of the form $10^*$ (open subsequences).

Initially $b(0,0) = 1$ and $b(0,x) = 0$ for $x > 0$. Let us now consider how to calculate $b(i+1,\cdot)$ given $b(i,\cdot)$. There are two possibilities to consider:

• If $a_{i+1} = 0$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ by attaching $a_{i+1}$ to any of the open subsequences. Thus $b(i+1,x) = xb(i,x)$ in this case.

• If $a_{i+1} = 1$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ in one of two ways: either it "closes" an open subsequences, or it forms a new open subsequences. Thus $b(i+1,x) = (x+1)b(i,x+1) + b(i,x-1)$.

The total number of partitions is then $b(n,0)$. Since $0 \leq x \leq n$, we can compute $b(n,0)$ in time $O(n^2)$ using dynamic programming.

As an illustration, here is a run of the algorithm on the sequence $1,0,1,1,0,1$. The columns correspond to $i$, and the rows to $x$:

$$ \begin{array}{c|cccccc} x/i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline 0 & 1 & 0 & 0 & 1 & 0 & 0 & 3 \\ 1 & 0 & 1 & 1 & 0 & 3 & 3 & 0 \\ 2 & 0 & 0 & 0 & 1 & 0 & 0 & 12 \\ 3 & 0 & 0 & 0 & 0 & 1 & 3 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \end{array} $$