You are given two things: A fixed initial 'model' partition of an interval, e.g.
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
and you are given 2, 11, 5, 12, i.e.
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!