3

I need this algorithm for one of my projects. I will paraphrase the problem.

There are 'n' ropes that have different colored rings on them. (The colors might repeat on the same rope or across different ropes).

My job is to pick a few of these ropes and join them such that all the colors in the n ropes are included in that joined rope. I should get the smallest rope size possible. I am allowed to cut each rope once and discard the end part if needed. There is one pre-defined end for each rope which should be used as the starting point incase that rope is included in the solution.

It will be nice to have exact solution for this.(This gives us something like a goal that our project is aiming to achieve). Can someone tell me how I might approach this? The n is about 10^5 for my work.

The total number of colors is also of the order of 10^5. The number of distinct colored rings on each rope ranges from 0 to about 10^3 at most.

  • Is there a bound on the number of colors? – jozefg Feb 5 '14 at 0:21
  • Are you able to choose which end of the rope you keep? Or is one end pre-defined as the starting point, and the other can be discarded? – SailsMan63 Feb 5 '14 at 4:27
  • Reduce to SAT or weighted SAT or (weighted) CSP. This will make it possible to use solvers that can probably find the optimal solution for your problem sizes. – ziggystar Feb 5 '14 at 12:39
  • @jozefg I've edited the question to indicate this – Phani Feb 6 '14 at 2:20
  • @SailsMan63 Yes, there is one pre-defined end for each rope which is the starting point. – Phani Feb 6 '14 at 2:21
2

(In this answer, I'm going to replace “rope” by “string”. I will use the made-up term “xfix” to mean “either a prefix or a suffix”.)

There is of course the brute force solution where we define an arbitrary ordering between the strings and then write a simple search over all possible combinations of string parts. The problem with this is that a naive implementation operates in O((2·l)n), where l is the average length of a string. With your magnitude for n, this is not feasible although memoization could make the pain bearable: The problem can be defined recursively, with a set of missing colors and a list of available strings being passed to each invocation. As the same input will be specified very often in the search tree, the optimal answer can be cached.

def optimal_combination(strings, colors):
  string = strings[0]
  remaining_strings = strings[1, ...]
  solution = None
  foreach xfix in string:
    remaining_colors = colors except colors in xfix
    possible_solution = xfix + optimal_combination(remaining_strings, remaining_colors)
    solution = possible_solution if solution.length < possible_solution.length
  return solution

Before we fall back to such brute force methods, we might want to limit the search space. Especially, I am going to assume that the number of colors is much smaller than the number of strings. We can now consider two trivial solutions:

  • One rope contains an xfix that contains each color exactly once. This xfix is then the solution.
  • Each color occurs at the end of a string, so that the solution is a sequence of substrings of length 1.
  • … and all the variants in between, i.e. the solution is made up of substrings which each contain all their colors exactly once.

However it may occur that such a minimal-length solution is not possible, and that a color must occur repeatedly in the output. We can make the search easier by choosing an appropriate data structure. For each xfix, we can record the following metrics:

  • its length
  • the set of colors contained in the xfix
  • which string it originally belonged to

We can now iterate through all xfixes, and build a data structure that maps sets of colors to the shortest xfix containing all these colors. This operation takes only Oa = O(2 · l · n).

color_map = dict()

foreach string in strings:
  foreach xfix in string:
    colors = colors in xfix
    if color_map[colors].xfix.length > xfix.length:
      color_map[colors] = {
        xfix: xfix,
        string: string,
      }

At this point, it may still be possible to assemble a shorter string for a certain color set. We remove this possibility by iterating through all entries. An entry may either already be optimal (if the length is the same as the size of the color set, or if it was assembled). Otherwise, if it isn't optimal, we try assemble a shorter string from the smaller color sets, optimizing them as well if necessary (color sets of size 1 are always optimal). When combining two xfixes, care must be taken that they're not from the same string (but note that never will two prefixes or two suffixes of the same string be combined, as their color sets overlap). It may be sensible to sort the entries before iteration, thus guaranteeing that all smaller color sets are already optimal when they're used in a combination. When the data structure contains m entries (with m <= 2 · l · n), then sorting takes less than Ob = O(m · log m). I am not sure about the complexity class of this combination operation, as I'm not sure about the exact algorithm needed to combine smaller entries into that of a given color set.

Unresolved issue: I'm not quite sure how to make sure that no postfix and suffix of the same string can be used together – this might require tracking the set of all used strings in each data structure entry, and forbidding to combine those where the string sets overlap.

Depending on how the xfixes are combined exactly, it may be sensible to maintain a dictionary of sets of sets, which maps colors to all color sets that contain this color. This could be easily built alongside combining the xfixes if they're combined strictly bottom-up.

The data structure now only contains optimal xfixes, and we can assemble our target string from them, following the same rules as during combination. This may require a tiny bit of brute forcing, but most of the work should already have been done.


So far, this is more of an idea dump than a well-structured answer. I'll try to evolve these concepts during the day, and update when I have more insight.

  • Thank you so much for working on the problem. One thing I should have mentioned is that the number of colors is also of the order of 10^5. It is highly unlikely that all the colors are on one rope. The number of distinct colored rings on each rope ranges from 0 to about 10^3 at the maximum. Sorry for missing this in my original question. – Phani Feb 6 '14 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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