7
$\begingroup$

The Maximum Diversity Problem calls for choosing $m$ items from a list of $n$ items, such that the diversity defined as some metric distance between items is maximized.

I have a simpler problem, which I was hoping I could solve in a simpler manner. In my case I have a list of $n$ items each with a certain non-unique key. I want to chose $m$ items from my list so that the maximal number of items per key is minimized.

e.g., if my list is:

('a', 5), ('b', 4), ('c', 2), ('a', 6), ('b', 5)

and we must choose $m=3$ items, an optimal solution would be a list containing one item for each key.

Is there an algorithm for doing this that is simpler than those for the Maximum Diversity Problem?

$\endgroup$
5
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$
    – Raphael
    Aug 13, 2016 at 19:22
  • $\begingroup$ @Raphael - I'm not a CS major, so my own research led me to read about the Maximum Diversity Problem, but this does seem to be a bit of an overkill. I have some heuristics I thought of, but I don't think they're very efficient. This is a real life problem I'm encountering, not an assignment of any sort. $\endgroup$ Aug 13, 2016 at 19:30
  • $\begingroup$ If there are $k$ different keys then the pigeonhole principle implies that your maximum diversity is at least $\lceil m/k \rceil$; and this is achievable. $\endgroup$ Aug 13, 2016 at 20:24
  • $\begingroup$ @Yuvalfilmus - True. The question is how. $\endgroup$ Aug 13, 2016 at 20:32
  • $\begingroup$ Actually I take it back that it's always achievable. But it seems that a greedy strategy should work. $\endgroup$ Aug 13, 2016 at 20:48

2 Answers 2

3
$\begingroup$

The following algorithm should work.

The algorithm proceeds in several rounds. At each round, let $m'$ be the number of remaining items to take. Take one item per key, up to $m'$ items, and remove these items. If we took $m'$ items, the algorithm terminates. Otherwise, continue to the next round.

We leave the correctness proof (or a counterexample) to the reader.

$\endgroup$
1
  • $\begingroup$ Thanks! I added my own answer which should give the same solution in a single pass. $\endgroup$ Aug 14, 2016 at 13:39
3
$\begingroup$

Thinking about it a a bit more, I think I have a "one pass" algorithm for solving this.

Let there be $n$ items with $k$ keys, with $n_i$ items for each key. We want to choose $m_i\le n_i$, such that $\sum m_i = m$, and that $\max{m_i}$ is minimized.

Clearly, if for all $n_i$ we have $n_i > m/k$, we simply choose $m_i = m/k$. Otherwise, we use the following algorithm:

  1. Count the number of items for each key ($n_i$) and sort them in ascending order.
  2. While $n_i \le m/k$ set $m_i=n_i$
  3. For all $n_i > m/k$, choose $m_i = \left\lceil \frac{m - \sum_{j<i} m_j}{k-i+1}\right\rceil$

This algorithm should be $O(n)$ in the length of the list, assuming the number of different keys is negligible in comparison.

$\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.