24
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can we require that the subsets in the input are sorted? \$\endgroup\$ – Shaggy Feb 28 at 21:48
  • \$\begingroup\$ Since you're talking about sets of sets, can I confirm that each input won't have repeated elements? \$\endgroup\$ – xnor Feb 28 at 23:35
  • \$\begingroup\$ @xnor yes, you may assume that no elements are repeated. \$\endgroup\$ – Zachary Hunter Feb 28 at 23:36
  • \$\begingroup\$ @Shaggy No. You cannot assume the input is sorted. \$\endgroup\$ – Zachary Hunter Feb 28 at 23:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Jonah Feb 29 at 18:00

10 Answers 10

12
\$\begingroup\$

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!

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

Japt -e, 15 13 10 bytes

Vcà mÍdeUn

Try it

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Does not handle the empty set correctly. Seems to always return false if you put, [] in A. \$\endgroup\$ – Zachary Hunter Feb 28 at 23:47
  • \$\begingroup\$ 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 \$\endgroup\$ – Zachary Hunter Feb 29 at 0:00
  • 1
    \$\begingroup\$ I think that's right now, @ZacharyHunter. \$\endgroup\$ – Shaggy Feb 29 at 10:12
3
\$\begingroup\$

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

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!

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

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 37 bytes

⊞υAFυ«≔⊟ιθ≔⊟ιι¬ιFιFθ¿¬⁻κλ⊞υ⟦⁻ι⟦κ⟧⁻θ⟦λ

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:

⊞υAFυ«

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.

FιFθ¿¬⁻κλ

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

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

δKøœεÅ/˜g}ß

Try it online!

| improve this answer | |
\$\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.