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.
- For every index into R:
- 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.
