Embedding Sets of Sets

Question

Setup: For two sets \$A,B\$, we say \$A \subseteq B\$ if every element in \$A\$ is also in \$B\$.

Another way of saying this, is that we can order the elements of \$A,B\$ into two lists \$L_A,L_B\$, such that \$L_A[i] = L_B[i]\$ where \$i\$ ranges over the indices of \$L_A\$.

We proceed to extend this idea, to define the relation \$\preceq\$. For two sets of sets, \$A,B\$, we say that \$A\preceq B\$ if we can arrange their elements into lists \$L_A,L_B\$, such that \$L_A[i]\subseteq L_B[i]\$ for all indices of \$L_A\$.

Task: Make a program/function which takes two sets of sets, A,B, determines if A ⪯ B as defined in the set up, and then appropriately returns Truthy or Falsy.

Input: You may give A and B to your input as sets. It is up to you how you wish have your function take A and B, be it separately, as a tuple, etc.

If you so choose, or if your language forces your hand, you can enter your input as lists, frozen sets or even submit elements one by one. Likewise, you may choose the datatype to represent the sets inside A and B.

For simplicity's sake, one may assume the elements of the sets in A and B are all integers.

Output: You can define whatever conditions you want to indicate your Truthy and Falsy inputs, as long as these conditions are independent of the output. (e.g. you can say "if my program never halts, this means Falsy")

Examples, with (1,0) indicating (Truthy, Falsy) respectively

A = {{4004,1}}, B = {{4},{4004,1}} => 1
# L_A = [{4004,1}], L_B = [{4004,1},{4}]

A = {{1,2},{5},{8}}, B = {{3,5},{6},{8},{7}} => 0
# {1,2} is not a subset of any set in B

A = {{4,44},{44,444},{4}}, B = {{4,44,444},{4,14},{4,40,44}} => 1
# L_A = [{4,44},{44,444},{4}], L_B = [{4,40,44},{4,44,444},{4,14}]

A = {{1,2,4},{6}}, B = {{1,2},{4},{6}} => 0
# {1,2,4} is not the subset of a single set in B, only the union of B

A = {{1},{1,2},{2}}, B = {{1,3},{2,3},{1,2}} => 1
# L_A = [{1},{1,2},{2}], L_B = [{1,3},{1,2},{2,3}]

A = {{-1},{8},{}}, B = {{-1,8,2},{8,-1,0}} => 0
# There are three elements in A, but only 2 in B, so the last item in L_A will not 
# be paired with a superset, even for the empty set, {}. (vacuity be damned)

A = {{-1},{8},{}}, B = {{0,8},{9,-1},{100}} => 1
# L_A = [{-1},{8},{}], B =[{0,8},{9,-1},{100}]

A = {{1,2}{3,4}}, B = {{1,2,3,4},{}} => 0
# {1,2} and {3,4} are each subsets of {1,2,3,4}, and are not subsets of any other 
# set in B, thus in the list, one of these will not be paired with their superset

Answer 1

Python 3, 84 62 58 bytes

Recursive function, A is a list of sets and B is a frozenset; returns false if \$A\preceq B\$ and true otherwise.

f=lambda A,B:A and all(A[0]-b or f(A[1:],B-{b})for b in B)

@PoonLevi and @SurculoseSputum helped save a great amount of bytes.

Explanation:

If A and B satisfy the relationship described, then this recursive statement makes sense:

The first set in A is contained in some i-th element of B and A', B' also satisfy the relationship, where
A' is A without the first set
B' is B without the said i-th element

Because I am returning the reverse, I am actually ensuring that, if the first element of A is contained in some element of B, then A' and B' cannot satisfy the relationship.

Try it online!

Answer 2

Japt -e, 15 13 10 bytes

Vcà mÍdeUn

Try it

Answer 3

J, 32 bytes

#@[e.[:#@~.@>@,@{[:<@I.0=#@-.&>/

Try it online!

Left arg is A, right is B.

• #@[ Is the len of A?...
• e. an element of?...
• [:#@~.@>@,@{ any of the lengths, after deduping, of the cartesian product of...
• [:<@I. the indexes with value 1 in each row of the matrix defined by...
• 0= elements that equal zero of...
• #@-.&>/ the function table / (like a multiplication table) defined by "the length after set substraction", i.e., whose (i,j) element is the length of the j-th element of B set subtracted from the i-th element of A.

Answer 4

Python 3, 110 107 bytes

Simply try to match A with all permutations of B.

Take input as 2 lists of sets, and output False if \$A \preceq B\$, and True otherwise. (Note that the truthiness is reversed).

lambda A,B:len(A)>len(B)or all(any(a-b for a,b in zip(A,P))for P in permutations(B))
from itertools import*

Try it online!

Answer 5

Jelly, 16 bytes

fƑ"Ạ¥ⱮŒ!}Ẹa,LÞƑ¥

Try it online!

A dyadic link taking A as its left argument and B as its right. Returns 1 for true and 0 for false.

Added 6 bytes to more correctly handle the situation when the length of A is more than the length of B. The previous test case worked only because the extra set was empty.

Explanation

    ¥ⱮŒ!}        | Using each permutation of B in turn as the right argument:
fƑ"              | - Check whether A is invariant when filtered pairwise to that permutation of B 
   Ạ             | - All true
         Ẹ       | Any true
          a    ¥ | And the following is true for the original arguments:
           ,     | - Pair
            LÞƑ  | - Invariant when sorted by length

Answer 6

Julia 1.0, 61 bytes

f(a,b)=a==[]||any(a[1]⊆x&&f(a[2:end],setdiff(b,x)) for x=b)

Try it online!

Answer 7

JavaScript (ES6),  79  77 bytes

Takes input as (B)(A), where \$B\$ is a list of sets and \$A\$ is a list of lists. Returns a falsy value (false or undefined) if \$A\preceq B\$, or true otherwise.

B=>g=([a,...A],u)=>a&&B.every((b,i)=>u>>i&1|a.some(v=>!b.has(v))|g(A,u|1<<i))

Try it online!

Answer 8

Charcoal, 37 bytes

⊞υＡＦυ«≔⊟ιθ≔⊟ιι¬ιＦιＦθ¿¬⁻κλ⊞υ⟦⁻ι⟦κ⟧⁻θ⟦λ

Try it online! Link is to verbose version of code. Takes input as a list of list of lists and outputs nothing if A is not a subset of B, otherwise the number of ways it found to verify that A is a subset of B as a string of -s (would be +1 byte to output just a single -). Explanation:

⊞υＡＦυ«

Perform a breadth-first search starting with the original input.

≔⊟ιθ≔⊟ιι

Extract the latest pair of sets to check.

¬ι

If A is (now) empty then it is a subset of B.

ＦιＦθ¿¬⁻κλ

Find all pairs of sets in A and B such that one is a subset of the other.

⊞υ⟦⁻ι⟦κ⟧⁻θ⟦λ

For each such pair, add the sets with those elements removed to the search.

Answer 9

Ruby, 60 45 bytes

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

Try it online!

How:

Recursively check: for every x in a

->a,b{a.all?{|x|                            }

there is at least a y in b

                b.any?{|y|                }

Such that removing x⋂y from a and y from b, the condition is still valid.

                          f[a-[x&y],b-[y]]

Sorry, what?

A and B are sets of sets. If A is empty, the function returns true. If B is empty and A is not empty, then the function returns false. So far, so good.

Otherwise, let's check what happens if we remove the sets as specified:

• if x⊆y then x⋂y==x. We remove x from A and y from B, then check if the remaining sets satisfy the initial condition recursively, until A or B is empty.
• if x⊄y but x⋂y is contained in A, we remove it anyway. We will check the same x again on a different y in the next iteration. We need to remove an item from A and B, we are just removing them in a different order, and that won't affect the final result.
• if x⊄y and x⋂y is not contained in A, we can continue: x won't be removed in the next iterations, and the check will fail as soon as B is empty.

Answer 10

05AB1E, 11 bytes

Outputs 0 if A⪯B, a positive integer otherwise.

δKøœεÅ/˜g}ß

Try it online!