# Embedding Sets of Sets

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

• Can we require that the subsets in the input are sorted? – Shaggy Feb 28 '20 at 21:48
• Since you're talking about sets of sets, can I confirm that each input won't have repeated elements? – xnor Feb 28 '20 at 23:35
• @xnor yes, you may assume that no elements are repeated. – Zachary Hunter Feb 28 '20 at 23:36
• @Shaggy No. You cannot assume the input is sorted. – Zachary Hunter Feb 28 '20 at 23:41
• Suggest falsy test case: A = {{4004 2} {1}} and B = {{1} {4004 1}}. My original solution was passing all the current test cases but would have incorrectly returned true for this. – Jonah Feb 29 '20 at 18:00

# Python 3, 8462 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.

• Took me a minute to understand why this works. Quite clever – Cruncher Feb 28 '20 at 20:44
• I actually think this may fail some test cases because of how greedily is selects the subset – Cruncher Feb 28 '20 at 20:45
• See the comment I wrote while you were typing that :) – Cruncher Feb 28 '20 at 20:48
• 62 bytes, with B being a set of frozensets – Tipping Octopus Feb 28 '20 at 22:56
• @PoonLevi wow, I was having problem with set not being hashable, but frozen set solved it! 58 bytes by returning the negated answer. – Surculose Sputum Feb 28 '20 at 23:13

# Japt-e, 1513 10 bytes

Vcà mÍdeUn


Try it

• Does not handle the empty set correctly. Seems to always return false if you put, [] in A. – Zachary Hunter Feb 28 '20 at 23:47
• I didn't write in the spec but it's in 3rd and 2nd to last test cases. I'll add that into the text of the question in a bit – Zachary Hunter Feb 29 '20 at 0:00
• I think that's right now, @ZacharyHunter. – Shaggy Feb 29 '20 at 10:12

# 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.
• The tio currently outputs ones for all of the test cases. – Zachary Hunter Feb 29 '20 at 6:56
• That’s because they’re all passing. Each line begins echo <x> = ... where x is the expected outcome for that case – Jonah Feb 29 '20 at 14:16
• Oh I see! My bad, I mostly know python. – Zachary Hunter Feb 29 '20 at 14:29

# 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!

• I was writing something similar using all, any and permutations. Got stuck where I needed zip. +1 – Cruncher Feb 28 '20 at 20:30
• @Cruncher don't want to be annoying, but you might also like my Python answer that doesn't use explicit permutations :) – RGS Feb 28 '20 at 20:38

# 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


# 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!

# 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!

# 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.

# 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.

# 05AB1E, 11 bytes

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

δKøœεÅ/˜g}ß


Try it online!