Permute the subintervals of an interval partition to most closely align with a model partition You are given two things: A fixed initial 'model' partition of an interval, e.g.

I------I---I-----I-------I----...


where each - or I represents an element in a discrete time series and the Is are the partition boundaries.  This can also be represented as a sequence of subinterval lengths, i.e. 7, 4, 6, 8, ...

Then, you're given a new set of subinterval lengths; and the task is to arrange these in such a way as to get as many coincident Is as possible.  Or equivalently, you are given a new partition on an interval of the same length (though, critically, the new partition may have greater or fewer elements) and the task is to shuffle the subintervals around to maximize alignment.  So if the model was

I------I---I-----I-------I----I


and you are given 2, 11, 5, 12, i.e.

I-I----------I----I-----------I


then the solution would be 11, 2, 12, 5, 

I----------I-I-----------I----I
           *             *


achieving alignment at 2 locations (marked with an asterisk, compare to model).

There is an additional constraint: The locations of the aligned subintervals must be distributed approximately randomly throughout the length of the solution.  The simplest means of getting a partition with at least some alignment to the model would be to build the new partition segment by segment, drawing without replacement from the collection of test segments, aligning where possible.  But this would strongly bias the occurrences of alignment towards the beginning of the time series, and is therefore not allowed.  There is of course also the brute force O(n!) enumeration but my series are little too long for that.

Naturally a solution that finds the optimal permutation would be great, but one that is efficient and gets a permutation with a substantial fraction of the possible alignment would also be good.  My current version is a variation on the 'simple' algorithm derived above, except only drawing from a small subcollection of subintervals so as to avoid bias.  I know it can be improved upon!
You can use integer linear programming (ILP) to solve this.  In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ alignment points (including the two endpoints).  Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment.

Call a "block" the (non-empty) sequence of consecutive intervals between two alignment points.  The left and right endpoint of the interval are automatically alignment points.  If there are $k+1$ distinct alignment points (including these two endpoints), there will be $k$ blocks.

Let $\ell_1,\ell_2,\dots,\ell_n$ be the set of lengths of the first set of subintervals, and $\ell^*_1,\ell^*_2,\dots,\ell^*_{n^*}$ be the lengths of the second set of subintervals.  These are constants provided as input.

Introduce zero-or-one unknowns $x_{i,j}$ (for $1\le i\le n$ and $1 \le j \le k$), with the intent that $x_{i,j}=1$ means that the $i$th subinterval (of length $\ell_i$) from the first partition will end up in the $j$th block.  Similarly, introduce zero-or-one unknowns $x^*_{i,j}$, with the intent that $x^*_{i,j}$ means that the $i$th subinterval (of length $\ell^*_i$) from the second partition will end up in the $j$th block.

Now we get a set of linear inequalities, as follows:


$\sum_i \ell_i x_{i,j} = \sum_i \ell^*_i x^*_{i,j}$, for all $j$.  (This is two ways of representing the length of the $j$th block.)
$\sum_j x_{i,j} = 1$ (each subinterval from the first partition ends up in exactly one block) and $\sum_j x^*_{i,j} = 1$.
$x_{i,j} = 1 \land x_{i+1,j}=0 \implies x_{i+1,j+1} = 1$ (i.e., each block starts where the previous one ended).   This can be expressed as the ILP constraint $x_{i,j} - x_{i+1,j} \le x_{i+1,j+1}$.  Similarly for the $x^*$'s.
$x_{i,j} = 1 \land x_{i'',j} = 1 \land i &lt; i' &lt; i'' \implies x_{i',j}=1$ (i.e., the subintervals in a block are consecutive).  This can be expressed as the ILP constraint $x_{i,j} + x_{i'',j} - 1 \le x_{i',j}$ for all $i,i',i''$ with $i &lt; i' &lt; i''$.  Similarly for the $x^*$'s.
$x_{1,1} = 1$, $x^*_{1,1} = 1$, $x_{n,k}=1$, $x^*_{n^*,k}=1$.


Of course, in the worst case ILP can take exponential time, but ILP solvers are pretty good and often perform well on many real-world problems, so it is probably worth a try.

(You could also try coding this up using a SAT solver, but you'd need to implement arithmetic, so a front-end like STP would probably be a better bet than a plain SAT solver.)