1
$\begingroup$

The title isn't the most explanatory or accurate since I had issues putting it into just a few words so here we go. I have a real-world problem and managed to find an inefficient solution that my computer is barely able to find before running out of RAM. I'm interested to find out if my problem is unique or if there is already a name for it and possibly much better algorithms.

Real-world problem description There's a TV show where they have a certain number of clips(~30) that they repeatedly show in an arbitrary, changing order with a good amount of repetitions before having shown all of them. I made a recording and want to cut them into one video that contains all of the clips without any repetition. I want to make as few (imperfect) cuts as possible.

My attempt at formalizing this issue

  • There's a set of items C(for clips). It doesn't have any duplicates and the order of elements does not matter.
  • There's an ordered set of indices into C. I call that R(for Recording). This is basically a chapter list of the recording which tells us where we can find which clip. Repetition is allowed.
  • There's something I call a group G, which is a list of consecutive indices into R. Or in programming terms, a range.
  • There's something I call a Sequence S, which is a list of Groups that forms the final solution that I'm looking for. The groups must not overlap each other. The sequence must contain every clip exactly once. Note that there's some indirection here since the groups contain indices into R which then gives us an index into C. There may me multiple solutions so an algorithm would produce multiple S.

My algorithm for finding the solution

  • We'll create state for every attempt to find groups. That state contains a sequence S, a list of indices into C (clips) that are part of one of the groups, and a list of indices into R(recording) that are part of one of the groups.
  • Create initial state-array: For every index into R, we'll create a group that's as big as possible. We only consider later indices, not earlier ones. We'll stop increasing the group size as soon as we hit an index into R, that describes a clip that we've considered already. When we found a group, we'll add it to the state, and mark the clip and recording position as used in their respective arrays. To prevent duplicates, we check if a newly found group is fully contained by the previous group and we'll skip adding state for it.

Now we'll enter the main loop. With every iteration we'll add one more group to every state and we'll stop as soon as there's any state(containing a sequence S) that covers all possible clips in C. We will also add a bunch of new states with every iteration, but all of them will have the same number of groups inside their S.

  • create a new, empty list of states States2
  • For every state in our list of states:
    • For every index into R:
      • Create a group that's as big as possible. We only consider later indices, not earlier ones. We'll also make sure to not create any groups containing clips that were already considered. Once found we'll clone the current state, fill in the new group, and insert it into States2. Effectively, we'll find every possible way to add another group to the current list. This is why the number of states in our list will increase a lot with every iteration.
  • make States2 replace the original list of states

At the end of that loop we'll have a list of states with both unfinished and finished sequences. You can remove the unfinished ones and remove duplicates(which exist, I guess that's a hint that the algorithm could be more memory effecient). Now you have unique Sequences S.

$\endgroup$
1
  • 1
    $\begingroup$ Could you give a complete example showing groups and recordings ? (with a few clips) $\endgroup$
    – user16034
    May 2, 2023 at 8:09

2 Answers 2

0
$\begingroup$

This is a kind of exact cover problem, one where you want to minimize the size of the cover (i.e., minimize the number of sets selected to be in the cover). Here, each potential range forms a set, containing the clips that are found in that range.

A plausible approach would be to use a SAT solver or ILP solver. In particular, you can use the standard ILP formulation of the set cover problem to express this as an instance of integer linear programming, then apply an off-the-shelf ILP solver. There are no guarantees, as the worst-case complexity of the problem is exponential, but for the problem size you mention, I suspect this would be successful at finding the optimal solution in a reasonable amount of time.

$\endgroup$
0
$\begingroup$

A possibly more efficient algorithm would use dynamic programming. For any subset of the clips $S\subseteq C$ and starting time $t$, calculate and memoize the minimum number of cuts needed to extract the clips in $S$ from the recording starting at time $t$. This gives an algorithm with $O(|R| \cdot 2^{|C|})$ worst-case complexity, but if you filter out unnecessary subproblems (for instance those where $S$ contains a clip that is not present in the recording from time $t$ onwards) you might get an algorithm that works for instances with moderately small sets $C$. In any case, I expect that this algorithm will be much more efficient than the one you have described in your post.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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