Compute the Join and Meet of Partitions

Question

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.

Answer 1

CJam, 32 - 10 = 22

q_~{_{T&},:U-U:+a+}fTp~m*::&La-p

::& is newer than this question.

CJam, 36 - 10 = 26

q_~{:T;_{T&},:U-U:+a+}/p~m*{~&}%La-p

Input:

[[0] [1] [2 3 4 7 6]]
[[2 3] [4 7] [6] [1 0]]

Output:

[[2 3 4 7 6] [0 1]]
[[0] [1] [2 3] [4 7] [6]]

Explanation

q                 " Read the input. ";
_~                " Evaluate a copy. ";
{:T;              " For each list T in the second partition: ";
    _{T&},        " Select all lists in the first partition which share items with T. ";
    :U-           " Save to U and remove them from the first partition. ";
    U:+a+         " Append the union of U to the first partition. ";
}/
p                 " Print the meet. ";
~                 " Evaluate another copy. ";
m*                " Get the Cartesian product. ";
{~&}%             " Get the intersections of each pair of lists. ";
La-               " Remove empty lists. ";
p                 " Print. ";

Answer 2

Java: 2014 (-10) = 2004 bytes

import java.util.*;public class A{static List<List<Set<Integer>>>b(Integer[][]c,Integer[][]d){Integer[][]e;Integer[][]f;if(c.length<=d.length){e=c;f=d;}else{e=d;f=c;}
Q g=h(e);List<List<Set<Integer>>>i=new ArrayList<>();i.add(j(f,g));i.add(k(f,g));System.out.println(i.toString());return i;}
static List<Set<Integer>>j(Integer[][]l,Q m){for(Integer[]o:l){if(o.length>1){n(m,o);}}
return p(m);}
static List<Set<Integer>>k(Integer[][]q,Q r){List<Set<Integer>>s=new ArrayList<>();for(Integer[]t:q){for(Set<Integer>u:v(r,t).values()){s.add(u);}}
return s;}
static Map<R,Set<Integer>>v(Q w,Integer[]x){Map<R,Set<Integer>>y=new HashMap<>();for(Integer z:x){R a=w.getSubset(z);if(!y.containsKey(a)){y.put(a,new HashSet<>());}
y.get(a).add(z);}
return y;}
static List<Set<Integer>>p(Q partition){partition.b();List<Set<Integer>>c=new ArrayList<>();for(R d:partition.y){Set<Integer>e=new HashSet<>();R f=d;while(f!=null&&!f.g){e.addAll(f.t);f.g=true;f=f.s;}
if(!e.isEmpty()){c.add(e);}}
return c;}
static void n(Q h,Integer[]i){for(int j:i){R k=h.getSubset(j);for(int l:i){R m=h.getSubset(l);if(k.s==null&&k!=m&&k!=m.s){k.s=m;}}}}
static Q h(Integer[][]n){List<R>o=new ArrayList<>();for(Integer[]p:n){o.add(new R(p));}
return new Q(o);}}
class R{R s;Set<Integer>t;boolean g=false;R(Integer[]u){this.t=Collections.unmodifiableSet(new HashSet<>(Arrays.asList(u)));}
R(Set<Integer>v){this.t=Collections.unmodifiableSet(v);}@Override
public int hashCode(){final int p=31;int r=1;r=p*r+((t==null)?0:t.hashCode());return r;}@Override
public boolean equals(Object x){if(this==x)
return true;if(x==null)
return false;if(getClass()!=x.getClass())
return false;R other=(R)x;if(t==null){if(other.t!=null)
return false;}else if(!t.equals(other.t))
return false;return true;}}
class Q{List<R>y;R getSubset(Integer z){for(R a:y){if(a.t.contains(z)){return a;}}
return null;}
Q(List<R>b){this.y=b;}
void b(){List<R>c=new ArrayList<>();for(int i=0;i<y.size();i++){if(y.get(i).s!=null){c.add(y.get(i));y.remove(i);}}
c.addAll(y);this.y=c;}}

Run by calling the b() function with two Integer[][].

Using the given inputs, outputs are:

[[[1]], [[1]]]
[[[0, 1, 2, 3]], [[0, 1], [2], [3]]]
[[[0, 1], [2, 3, 4, 6, 7]], [[2, 3], [4, 7], [6], [1], [0]]]
[[[0, 1, 2, 3, 4, 5, 6]], [[3], [0], [6], [4], [2], [5], [1]]]

Answer 3

Mathematica, 127 - 10 = 117

Not fully golfed.

{ConnectedComponents@Graph@Union@##,FindClique[Graph@Intersection@##,Infinity,All]}&@@(Union@@(Rule@@@Tuples[#,2]&/@#)&/@{##})&