Embedding Sets of Sets

Question

Set Up: 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

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 3

Japt -e, 15 13 10 bytes

Vcà mÍdeUn

Try it

Answer 4

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 5

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 6

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 7

Ruby, 60 45 bytes

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

Try it online!

How:

Check that for each element in A there is an element of B satisfying x ⊆ y. The check uses a shortcut: if x ⊆ y, then x&y==x, we can remove x from A and Y from B and check the remaining element. Otherwise, two different things can happen: we don't remove anything from A (and the comparison will fail in the recursion) or we remove a different item, which is not wrong if it gets the right result in another iteration.

Answer 8

Jelly, 10 bytes

fƑ"Ạ¥ⱮŒ!}Ẹ

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.

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