6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ May one provide two functions? \$\endgroup\$ – xnor Jan 4 '15 at 13:57
  • \$\begingroup\$ @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). \$\endgroup\$ – Zgarb Jan 4 '15 at 14:04
  • \$\begingroup\$ @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. \$\endgroup\$ – Zgarb Jan 4 '15 at 14:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Optimizer Jan 4 '15 at 18:40
  • 1
    \$\begingroup\$ It'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. \$\endgroup\$ – Peter Taylor Jan 4 '15 at 22:43
7
\$\begingroup\$

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. ";
\$\endgroup\$
  • 1
    \$\begingroup\$ That is impressively short. \$\endgroup\$ – Martin Ender Jan 4 '15 at 15:34
1
\$\begingroup\$

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]]]
\$\endgroup\$
  • 1
    \$\begingroup\$ and a downvote is because ? \$\endgroup\$ – PoweredByRice Jan 4 '15 at 21:01
  • 2
    \$\begingroup\$ It might be worth dropping in to Code Golf Chat to ask about what can be improved and get a feel for the site. I find it very helpful for myself. \$\endgroup\$ – trichoplax Jan 4 '15 at 21:19
  • \$\begingroup\$ @Nhan — I don't know why you were downvoted either. I just voted your answer up. \$\endgroup\$ – Todd Lehman Jun 16 '15 at 16:04
0
\$\begingroup\$

Mathematica, 127 - 10 = 117

Not fully golfed.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.