6
Background
In this challenge, a partition of a set S
means a collection of nonempty subsets of S
, which are mutually disjoint and whose union is S
. We say that a partition p
is finer than another partition q
(and q
is coarser than p
), if it can be obtained from q
by splitting some of its sets into smaller pieces. The join (or least upper bound) of two partitions is the finest partition which is coarser than both of them, and their meet (or greatest lower bound) is the coarsest partition which is finer than both of them. See the Wikipedia pages on partitions and lattices for more information and nice pictures.
One way to compute the join and meet of two partitions p
and q
is the following. Form a graph whose vertex set is S
, and add an edge a - b
for each pair a, b
that are in the same set in either p
or q
. Then the join of p
and q
contains the connected components of this graph. The meet of p
and q
consists of all nonempty intersections of a set in p
with a set in q
.
For example, consider the partitions [[0,1],[2,3]]
and [[0,1,2],[3]]
of S = [0,1,2,3]
. The graph mentioned above is
0-1
|/
2-3
where the edge 2 - 3
comes from the first partition (2
and 3
are in the same set), and the triangle comes from the second one (0
, 1
and 2
are in the same set). This means that the join is [[0,1,2,3]]
. The intersections of all the sets in the partitions are
[0,1] ∩ [0,1,2] = [0,1],
[0,1] ∩ [3] = [],
[2,3] ∩ [0,1,2] = [2],
[2,3] ∩ [3] = [3]
Removing the empty set, we have the meet [[0,1],[2],[3]]
.
Input
Two partitions of a finite set of integers, given as arrays of arrays.
Output
The join and meet of the input partitions, in this order.
Test Cases
[[1]] [[1]] -> [[1]] [[1]]
[[0,1],[2,3]] [[0,1,2],[3]] -> [[0,1,2,3]] [[0,1],[2],[3]]
[[0],[1],[2,3,4,7,6]] [[2,3],[4,7],[6],[1,0]] -> [[0,1],[2,3,4,6,7]] [[0],[1],[2,3],[4,7],[6]]
[[0],[1,2],[5,4],[3,6]] [[0,3],[6,4],[5,2],[1]] -> [[0,1,2,3,4,5,6]] [[0],[2],[1],[4],[5],[3],[6]]
Detailed Rules
The order of the sets in the output partitions, and of the numbers in those sets, does not matter. You can assume that the inputs are correct, that is, they contain the same numbers, each exactly once, and no empty arrays. Note that the numbers do not necessarily form an interval (the third test case contains no 5
).
You can write either a full program or a function. You can also write two programs/functions in the same language, one of which computes the join and other the meet, but there's a bonus of -10 bytes if you don't choose this option. The shortest byte count wins, and standard loopholes are disallowed.
May one provide two functions? – xnor – 2015-01-04T13:57:32.570
@xnor No, you must do it in one function. If you provide two functions, you also need to provide a third one that combines their outputs (wrapping them in a list or tuple or such). – Zgarb – 2015-01-04T14:04:11.093
@xnor On a second thought, I think I'll allow two functions, but give a bonus if you can do it in one. I'll edit the question. – Zgarb – 2015-01-04T14:36:32.140
In the 4th example, the join is not the finest partition. A finest partition would consist of a set of 3, 2, 2 numbers each. Same for the meet. – Optimizer – 2015-01-04T18:40:51.470
@Optimizer I don't see how that's possible. Do you have an example output? – Martin Ender – 2015-01-04T18:42:21.567
@Optimizer You can think of the operations like this. If two numbers are in the same set in either of the inputs, then they must be in the same set in the join. And if two numbers are in different sets in either input, then they must be in different sets in the meet. – Zgarb – 2015-01-04T21:51:16.837
1It's quite hard to find the "more info" in the Wikipedia article you link. It contains the word meet zero times, and the word join once, in the context of non-crossing partitions. It might be helpful to link first to a page about lattices or complete lattices, and then to the section of the page on partitions of a set which talks about the lattice structure of the refinement partial order. – Peter Taylor – 2015-01-04T22:43:42.947
@PeterTaylor You're right, and now that I tried, I actually couldn't find anything on how to actually compute the join and meet (without resorting to a Google Books preview). I added some explanation about this. I hope it is clear enough. – Zgarb – 2015-01-05T08:30:57.763