0
$\begingroup$

I have the following problem to solve:

Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size.

Place a total of $k$ instances of each symbol into some of the buckets of B, whereas there must not be two symbols of the same kind within one bucket (for each pair of symbols $(s_i,s_j)$ within $b_k$, $s_i \neq s_j$) and there must not be the same pair of two symbols within more than one bucket.

How many symbols can I place into the $n$ buckets?

I am looking for:

  1. A formula that provides $|S|$ depending on $n$ and $k$.
  2. An algorithm to find the perfect placement of $S$ into buckets such that $|S|$ is maximized.
  3. $K$ hash algorithms that provide (for fixed $n$, $k$) in constant time for each $s_i \in S$, the $k$ buckets $s_i$ should be placed such that the constraints above are fulfilled.

For 1. I believe the answer is 2^(log2(|B|) * 2 - k) which I derived from my current implementation but I don't have a good understanding of it.

For 2. I have designed the following algorithm: Define a hashset for each bucket b. Try to insert a symbol in a certain bucket by looking up said bucket. If the symbol already exists move on to the next bucket. Now determine whether the collision list of said symbol contains any other symbol of the bucket (set), if not insert the symbol and add all other symbols of the bucket to the collision list. In the case of a collision try the next bucket. Repeat until k instances of the symbol are inserted. The algorithm works but does not produce optimal results. In particular, the way of choosing the next bucket in the case of a failed collision affects the quality of the result.

Pseudo Code:

while(true) {
  sym = new symbol;
  collision_list = new empty list;
  while(inserted_symbols < k) {
    for each s in collision_list {
      if(!current_bucket.lookup(s)) {
        current_bucket.insert(s);
        collision_list.insert(all elements of current_bucket);
      }
    }
    current_bucket = next_bucket();
  }
  break if no symbol can be inserted anymore
}
$\endgroup$
  • 2
    $\begingroup$ I don't understand what you're asking. You say you want to place $k$ copies of each symbol into each bucket, but then you say you can't have even two copies of the same symbol in a bucket. Also, what did you try? Where did you get stuck? $\endgroup$ – David Richerby Oct 24 '16 at 7:59
  • $\begingroup$ @DavidRicherby I think they mean that each bucket gets $k$ different symbols. Plus, no combination of symbols may appear in more than one bucket. How many symbols do we need for that? $\endgroup$ – Raphael Oct 24 '16 at 11:19
  • $\begingroup$ I want to place the k symbols into a subset of B. (k<<|B|). $\endgroup$ – hlitz Oct 24 '16 at 15:51
  • $\begingroup$ @hlitz i have been trying to come up with a solution for this, one thing which i have noticed is the approach which you have followed in your solution is the greedy approach isn't it? As soon as we find a suitable bucket we fill it. The greedy method doesn't always gives an optimal solution. maybe that is the problem with the code. Can dynamic programming help here? $\endgroup$ – Shubham Singh rawat Oct 28 '16 at 16:17
  • $\begingroup$ @ShubhamSinghrawat Yes its greedy and not optimal. Can you elaborate on your dynamic programming idea? $\endgroup$ – hlitz Nov 2 '16 at 0:38

Your Answer

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

Browse other questions tagged or ask your own question.