Question

Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem.

Suppose you have 200 bins. Each bin would be very happy to have the integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9. And the algorithm would be very happy if all bins get that.

The algorithm is allowed to choose four 3-tuples from a collection of 800 3-tuples. It will assign assign 4 of them to each bin. So each bin will have four 3-tuples assigned to them. These 3-tuples have the following properties:

  1. They are pseudo-randomly generated all at once as a collection of 800 3-tuples.
  2. Each number in a generated 3-tuple is unique. For example, (1, 1, 2) and (7, 4, 4) are impossible but (1, 2, 3) and (8, 2, 9) are possible.
  3. Each value within the 3-tuple can only be a number from 1 to 9. For example, (10, 3, 15) is an impossible tuple. The 3 could occur, but 10 and 15 could not.

A corollary from point 1 is that it could be the case that some integers occur less than the amount of bins that exist. In such a case the application would be very happy if as many bins get a numerical sequence from 1 to 9 and the other bins get as close as possible to such a sequence. For example, suppose that the number 9 has been randomly generated in 180 3-tuples, then at least 20 bins will not get the number 9, but they hopefully should be able to get the integers 1 to 8.

Here is an example of 2 bins and 8 3-tuples. The following numbers are pseudo-randomly generated.

(3, 8, 2) 
(2, 1, 5) 
(2, 7, 8) 
(7, 8, 5)
(7, 8, 4)
(7, 5, 8)
(7, 9, 5)
(4, 7, 3)

Assigning them to two bins as optimal as possible by the requirements yields:

Bin 1 - Sequence: 1, 2, 3, 4, 5, 7, 8, 9
(2, 1, 5)
(4, 7, 3)
(7, 9, 5)
(7, 8, 5)

Bin 2 - Sequence: 2, 3, 4, 5, 7, 8
(2, 7, 8) 
(7, 8, 4)
(7, 5, 8)
(3, 8, 2)

Note: in this particular example there is no 6. There is one 1 and one 9. This means that the 1 and the 9 automatically go to Bin 1. The integer 6, well it simply isn't there, so it cannot be assigned to a bin.

My first question: Design an algorithm that ensures the most optimal solution.

My second question: is a generalized or analogous version known as a certain problem or field in mathematics?

I suppose this problem is a variant of the set cover problem. However, instead of covering a universe, 200 'universes' need to be covered. Or said in another way: the universe needs to be covered 200 times in such a way that the cover can be split up into 200 groups of four 3-tuples.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top