I'm looking for an algorithm to "pack" a collection of sets as slices of a sequence. I'm sure somebody must have thought about this before. Specifically the algorithm has
Input: F_1, .., F_n where the F_i are finite subsets of some S
Output: A (shortest) sequence s_1, .., s_m in S such that for all i there is a j where F_i = { s_k | j <= k < j + |F_i| }
Simplifications
- Without loss of generality we can assume all F_i are non-empty, the output doesn't change with added empty sets.
- Also we can assume F_i != F_j when i != j, the output also doesn't change when duplicates are added.
- Lastly we can assume S = union of all F_i and hence S is finite.
Observations
- The output is not unique: given { a } and { a, b } both ab and ba are shortest solutions.
- In fact if a sequence is a (shortest) solution the reverse sequence is also a (shortest) solution.
- The output may have to contain duplicates: given { a, b }, { a, c } and { b, c } a solution is abca, but there is no valid sequence of length 3