10
First, a few definitions:
- Given
n
andk
, consider the sorted list of multisets, where for each multiset we choosek
numbers from{0, 1, ..., n-1}
with repetitions.
For example, for n=5
and k=3
, we have:
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 2), (0, 2, 3), (0, 2, 4), (0, 3, 3), (0, 3, 4), (0, 4, 4), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), (3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]
- A part is a list of multisets with the property that the size of the intersection of all multisets in the part is at least
k-1
. That is we take all the multisets and intersect them (using multiset intersection) all at once. As examples,[(1, 2, 2), (1, 2, 3), (1, 2, 4)]
is a part as its intersection is of size 2, but[(1, 1, 3),(1, 2, 3),(1, 2, 4)]
is not, because its intersection is of size 1.
Task
Your code should take two arguments n
and k
. It should then greedily go through these multisets in sorted order and output the parts of the list. For the case n=5, k=3
, the correct partitioning is:
(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)
(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)
(0, 2, 2), (0, 2, 3), (0, 2, 4)
(0, 3, 3), (0, 3, 4)
(0, 4, 4)
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)
(1, 2, 2), (1, 2, 3), (1, 2, 4)
(1, 3, 3), (1, 3, 4)
(1, 4, 4)
(2, 2, 2), (2, 2, 3), (2, 2, 4)
(2, 3, 3), (2, 3, 4)
(2, 4, 4)
(3, 3, 3), (3, 3, 4)
(3, 4, 4), (4, 4, 4)
Here is another example for n = 4, k = 4
.
(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)
Clarification of what greedy means: For each multiset in turn we look to see if it can be added to the existing part. If it can we add it. If it can't we start a new part. We look at the multisets in sorted order as in the example given above.
Output
You can output the partitioning in any sensible format you like. However, multisets should be written horizontally on one line. That is an individual multiset should not be written vertically or spread over several lines. You can choose how you separate the representation of parts in the output.
Assumptions
We can assume that n >= k > 0
.
@LuisMendo I just made a mistake. I meant multisets should be written horizontally on one line. – None – 2017-04-16T17:10:56.757
In the first test case, why is
(0, 4, 4)
by itself? Given your description, I would think its "part" would be(0, 4, 4), (1, 4, 4), (2, 4, 4), (3, 4, 4), (4, 4, 4)
. Similarly for(0, 0, 3, 3)
in the second test case. – Greg Martin – 2017-04-16T19:00:02.540@GregMartin Because of the greediness of the method. You are right that it will in general be suboptimal. The minimal number of parts you can get by a non greedy method is an interesting if hard question, – None – 2017-04-16T19:05:10.990
Oh, you literally mean that once the very next term doesn't match the "active" part, then that part is closed forever. Ok. – Greg Martin – 2017-04-16T19:46:00.887