# Number of possible sequence partitioning

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

• Could you please mention where the problem comes from? What is the scale of the input data? – xskxzr Apr 11 '18 at 15:26
• seems input sequence always partitioned into 2 subsequences. If so then input that do not both start and end with 1 has no solution. Must the input always start and end with 1? – Apiwat Chantawibul Apr 11 '18 at 15:36
• Are you allowing subsequences of length 1? – Yuval Filmus Apr 11 '18 at 16:20
• Are you allowing subsequences to contain 1s inside? – Yuval Filmus Apr 11 '18 at 16:29
• @YuvalFilmus From his example, neither subsequences of length 1 nor subsequences containing 1s inside are allowed. – xskxzr Apr 11 '18 at 16:32

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}$$

• Your understanding of the problem is correct. Perfect answer, great explanation! – Beniamin Zamfir Apr 12 '18 at 14:01