1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Could you please mention where the problem comes from? What is the scale of the input data? $\endgroup$ – xskxzr Apr 11 '18 at 15:26
  • $\begingroup$ 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? $\endgroup$ – Apiwat Chantawibul Apr 11 '18 at 15:36
  • $\begingroup$ Are you allowing subsequences of length 1? $\endgroup$ – Yuval Filmus Apr 11 '18 at 16:20
  • $\begingroup$ Are you allowing subsequences to contain 1s inside? $\endgroup$ – Yuval Filmus Apr 11 '18 at 16:29
  • $\begingroup$ @YuvalFilmus From his example, neither subsequences of length 1 nor subsequences containing 1s inside are allowed. $\endgroup$ – xskxzr Apr 11 '18 at 16:32
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.