Selection distribution algorithm?

user_2213795 0
Viewed 58

I'm not even sure what kind of algorithm I need here. Let me describe the problem:

Assume I have a list of values: [1, 3, 3, 8, 19, 23]

And I have six collections:

A = [1, 2, 3, 3, 4, 5]
B = [10, 12, 13, 14, 19, 23]
C = [1, 2, 3, 8, 19, 20, 21, 24]
D = [3, 5, 6, 8, 10, 12, 13, 14]
E = [20, 21, 22, 23, 24, 25, 26]
F = [25, 26, 26, 27, 29, 30]

I want to pick out those values from the collections in a way that I try to pick from the most collections possible. In other words, even though I could obviously pick 1, 3, 3 from collection A, I'd rather pick from A, C, and D. So how do I write an algorithm that maximizes the number of collections that I pick from?

algorithm
2 Answers

I am not sure if this is truly and compellingly an optimization problem. Or - at least - if it should be approached as one. I am not even sure if I understood the question correctly. Also I do not know if the values taken from one of the collections should be removed or not.

But here I go, embarrassing myself...

What I understood: You try to get the values from as many of the collections A-F as possible.

So here is my idea how this could be accomplished. I am only not sure if this is provably an optimal solution.

Algorithm assumes that all values are contained in the collections (else it won't terminate).

Input: values

  1. Place all collections (A-F) into a circular array repo.
  2. Set index current to the start of repo.
  3. if no more values then done.
  4. if repo[current] contains head of values then move current to next position, remove head of values, goto 3. else move current to next position, goto 3.

Here an example program implementing this.

(defun distro (values &rest sources)
  (let* ((n-sources (length sources))
     (repo (make-array n-sources :initial-contents sources))
     (position 0))
    (labels ((next-position ()
           (setf position (if (< (1+ position) n-sources) 
                  (1+ position)
                  0)))
         (select (vals)
           (if vals
           (if (member (car vals) (aref repo position))
               (progn ; found a value in current source - switch source
             (format t "found ~D in list ~D~%"
                 (car vals) position)
             (next-position)
             (select (cdr vals)))
               (progn ; not found in current source - try next ones
             (next-position)
             (select vals))))))
      (select values))))

(defun distro-demo ()
  (distro '(1 3 3 8 19 23)
      '(1 2 3 3 4 5)
      '(10 12 13 14 19 23)
      '(1 2 3 8 19 20 21 24)
      '(3 5 6 8 10 12 13 14)
      '(20 21 22 23 24 25 26)
      '(25 26 26 27 29 30)))

And the output is...

found 1 in list 0
found 3 in list 2
found 3 in list 3
found 8 in list 2
found 19 in list 1
found 23 in list 4

user_22251040

This is an instance of a maximum bipartite matching problem. You can form a graph consisting of two types of nodes: one node for each number in your input list, and one node for each of the sets. You then add an edge from a number to a set if the number contains the set.

Your goal then is to select the greatest number of edges possible such that no number is assigned to two or more sets, which is exactly what max bipartite matching is all about. There are a number of fast algorithms for solving this problem; check the Wikipedia link for some initial ideas.

user_5015570
Related