Is this set laminar?

Question

A family of sets is called laminar if for any two sets \$A\$ and \$B\$ in the family one of the following is true:

• \$ A \subseteq B \$
• \$ A \supseteq B \$
• \$ A \cap B = \emptyset \$

Or less mathematical:

A laminar set is a list of lists that satisfies the following condition: If two elements of the top level list have at least one element in common, one of them has to be completely contained in the other one.

Examples:

laminar:
{} 
{{1,2,3},{1,2},{1},{}}
{{1,2,3,4},{1,2,3},{1,2},{3},{4}}
{{1,2,3,4},{1,2},{3,4},{1},{3}}
{{1,2,3,4},{1,3},{2,4},{1},{2},{3},{4},{}}
{{1,2,3},{4,5},{7,8},{3},{5},{7}}

not laminar:

{{1,2},{2,3}}
{{1,2,3,4},{1,2,3},{1,2},{3,4}}
{{1,2,3,4},{1,2},{3,4},{2,3},{1},{2},{3},{4}}
{{1,2,3,4,5},{1,2,3},{4,5,6}}

Your goal is to write a program of function that takes a set of set as input and returns truthy if the set is laminar and falsey if is it not laminar.

Rules:

• You can take lists instead of sets as Input
• If you use lists as input you can assume that the lists (top-level and/or sub-lists) are sorted (in any convenient order) and each element appear only once
• Your solution should be able to handle Inputs lists with at least 250 distinct element values
• You are allowed to use any type to represent the elements of the list (as long as it has enough distinct values)
• This is code-golf the shortest solution (per language) wins.

Answer 1

Python, 50 bytes

lambda c:all(a&b in(a,b,a-a)for a in c for b in c)

Attempt This Online!

Answer 2

Rust, 63 bytes

Port of mousetail's python answer.

|s|s.iter().all(|a|s.iter().all(|b|a&b==*a||a&b==*b||a&b==a-a))

Rust explorer

Answer 3

Nekomata + -e, 8 bytes

ᵒ{ᵋ∩?Ø?=

Attempt This Online!

ᵒ{ᵋ∩?Ø?=
ᵒ{          For each pair of elements A, B in the input, check that:
  ᵋ∩        Intersection of A and B
    ?Ø?     Any of A, B, or the empty set
       =    Are they equal?

Answer 4

JavaScript (ES6), 69 bytes

Expects a list of lists. Returns false for laminar, or true for not laminar.

Not the right tool for the job.

a=>a.some(x=>a.some(y=>(b=x.filter(v=>y.includes(v))+'')&&b!=x&b!=y))

Try it online!

41 bytes (ES11)

As one would expect, converting each sub-list to a BigInt bit-mask and applying bitwise logic is longer.

a=>(a=a.map(b=>b.map(v=>m|=1n<<v,m=0n)&&m)).some(x=>a.some(y=>y^(y&=x)&&x^y&&y))

Try it online! (80 bytes)

But if we can take the list of sets directly as a list of bit-masks (as suggested by @Cubic), then we can just do:

a=>a.some(x=>a.some(y=>y^(y&=x)&&x^y&&y))

Try it online!

Answer 5

05AB1E, 11 bytes

ãε¯ªy`Ã.å}P

Try it online or verify all test cases.

Explanation:

ã        # Cartesian product to get all pairs of the (implicit) input-list
 ε       # Map over each pair of lists:
  ¯ª     #  Append an empty list to the pair
  y`     #  Push the lists of the pair separately to the stack
    Ã    #  Pop both, and push a list with values that occurred in both lists
     .å  #  Non-vectorized check if this list is in the earlier triplet of lists
 }P      # After the map: check if all are truthy
         # (after which the result is output implicitly)

Answer 6

Raku, 47 bytes

{all cross @^a,@a,:with{$^x∩$^y≡∅|$x|$y}}

Try it online!

(The ageing version of Perl 6 on TIO does not understand the ≡ operator, added in 2020. I replaced it there with eqv for one additional byte.)

This anonymous function takes as input a list of sets in the variable @^a/@a. It computes the cross product of all of those sets with each other using the anonymous function in braces following :with. For each pair, that function returns a truthy value if the intersection (∩) of the two sets is identical to (≡) one of those sets or to the empty set (∅). The final result is a truthy value indicating whether all of those pairwise values are truthy.

Answer 7

JavaScript (Node.js), 88 bytes

x=>x.some(a=>x.some(b=>g(a,b)&g(b,a)))
g=(a,b)=>/0,1|1,0/.test(a.map(i=>+b.includes(i)))

Try it online!

Return inversed

Answer 8

Factor + math.unicode sets.extras, 52 bytes

[ dup '[ _ [ diffs f like and and ] with ∃ ] ∃ ]

Attempt This Online!

Output is inverted: outputs f for laminar and t for not laminar.

• ∃ alias for any? that is 1 byte shorter
• dup '[ _ [ ... ] with ∃ ] ∃ Is there any pair of sets in the input that is true when [ ... ] is applied to them?
• diffs A lovely word that takes two sets as inputs and returns three outputs: the set difference between input 1 and input 2, the set difference between input 2 and input 1, and the intersection between input 1 and input 2. This word converts empty sets to f except for the intersection.
• f like Convert the intersection to f if it is empty; leave alone otherwise.
• and and Take the logical and of the three results.

Answer 9

Haskell, 68 63 bytes

Unfortunately \\ is not in Prelude, and I couldn't figure out how to write it shorter without the Data.List functions (without the import it's 51 bytes).

(Shaved off 5 bytes by switching to list comprehension from nested all)

import Data.List
l s=and[a\\b==[]||b\\a==[]||a\\b==a|a<-s,b<-s]

Try it online!

Answer 10

Jelly, 8 bytes

iƇⱮFf\€Ƒ

Try it online!

Relies on the whole family being sorted descending by length, incidentally coinciding with how the testcases are displayed.

  ⱮF        For each element of any of the sets,
iƇ          filter the family to only sets containing it.
      €Ƒ    Is every one of those sub-families unchanged by
    f\      cumulative intersection?

Jelly, 10 9 bytes

fpḟpḟ@ðþF

Try it online!

-1 remembering that I already made the link dyadic

Outputs an empty list iff laminar. If output can't have reversed truthiness, slap a Ṇ on the end.

      ðþ     For every pair (dyadically) of sets:
 p           Take the Cartesian product of
f            the intersection and 
  ḟ          the difference one way
   p         and
    ḟ@       the difference the other way.
        F    Flatten.

Jelly, 10 bytes

Œcµḟṭif/)P

Try it online!

Direct approach everyone else is using.

Œcµ     )P    For every pair (as a list) of sets:
    ṭ         Append
   ḟ          the empty list;
     i        does that contain
      f/      the intersection?

Answer 11

Scala, 79 bytes

Port of @corvus_192's Rust answer in Scala.

---

Golfed version. Try it online!

s=>{s.forall(a=>{s.forall(b=>{var z=a intersect b;z==a||z==b||z==a.diff(a)})})}

Ungollfed version. Try it online!

import scala.collection.immutable.HashSet

object Main extends App {
  
  def f(s: Seq[HashSet[Int]]): Boolean = {
    s.forall(a => {
      s.forall(b => {
        a.intersect(b) == a || a.intersect(b) == b || a.intersect(b) == a.diff(a)
      })
    })
  }
  
  assert(f(Seq.empty[HashSet[Int]]))
  assert(f(Seq(
    HashSet(1, 2, 3),
    HashSet(1, 2),
    HashSet(1),
    HashSet.empty[Int]
  )))
  assert(f(Seq(
    HashSet(1, 2, 3, 4),
    HashSet(1, 3),
    HashSet(2, 4),
    HashSet(1),
    HashSet(2),
    HashSet(3),
    HashSet(4),
    HashSet.empty[Int]
  )))

  assert(!f(Seq(HashSet(1, 2), HashSet(2, 3))))
}

Answer 12

R, 64 bytes

\(x,`?`=all)?Map(\(A)?Map(\(B)any(?(p=A%in%B),?B%in%A,?!p),x),x)

Attempt This Online!

Answer 13

Charcoal, 15 bytes

⬤θ⬤θ№⟦ιλυ⟧⁻ι⁻ιλ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for laminar, nothing if not. Explanation: Charcoal has no set intersection function, otherwise this would be a direct port of @mousetail's latest Python answer, but emulating list intersection using list difference does mean I get to use the predefined variable for an empty list.

 θ              Input list
⬤               All elements satisfy
   θ            Input list
  ⬤             All elements satisfy
      ι         Outer element
       λ        Inner element
        υ       Empty list
    №⟦   ⟧      Includes
           ι    Outer element
          ⁻     List difference
             ι  Outer element
            ⁻   List difference
              λ Inner element

Answer 14

Pyth, 13 bytes

.Am}@Fd+d.{Y*

Attempt This Online!

Explanation

.Am}@Fd+d.{Y*QQ    # implicitly add QQ
                   # implicitly assign Q = eval(input())
            *QQ    # cartesian product of Q and Q
  m                # map over lambda d
    @Fd            #   intersection of the elements of d
   }               #   is in
       +d.{Y       #   d plus the empty set
.A                 # return whether all elements are true

Answer 15

Arturo, 56 bytes

$->x[some? x'a->some? x'b->¬∨∨a=a--b[]=a--b[]=b--a]

Try it!

Inverts the output; false for laminar and true for not laminar.

$->x[               ; a function taking a set of sets x
    some? x'a->     ; is there some set a in x that
        some? x'b-> ; is there some set b in x that
            []=b--a ; the empty set equals b diff a
            ∨       ; or
            []=a--b ; the empty set equals a diff b
            ∨       ; or
            a=a--b  ; a diff b is unchanged
            ¬       ; logical not (we have to do it this way to accommodate empty input)
]                   ; end function

Answer 16

C (GCC), 199 197 bytes

• -1 bytes thanks to @Unrelated String
• -1 bytes thanks to @ceilingcat

#define T int
#define A(p,z)*v){T b=0,i=0;for(;y;++i)b|=p;return b?z:!z;}
#define y v[i]
C(T x,T A(x==y,1)P(T z,T*s,T A(z-C(y,s),1)X(T*a,T*A(P(1,a,y)&P(1,y,a)&(P(0,a,y)|P(0,y,a)),0)f(T*A(!X(y,v),1)

Attempt This Online!

Takes input as a double pointer to int (int **) which is zero terminated on both levels (hence 0 cannot be used as an element).

Note that the solution is in C, while the full snippet is in C++ because I used vectors to store the data after parsing.

---

ungolfed solution (in C++)

Answer 17

Julia 1.0, 43 bytes

~x=all(A⊆B||B⊆A||A∩B==[] for A=x,B=x)

Try it online!

-2 bytes thanks to MarcMush: square brackets aren't needed for an array comprehension that is passed to a function

Answer 18

Ruby, 45 43 bytes

->a{a.all?{|x|a.all?{|y|[[],x,y].any?x&y}}}

Try it online!