8
$\begingroup$

How could one create a code that checks whether a set is a subset of another, but not ignoring the duplicates? For example, $\{1,1,1\}$ would be a subset of $\{1,1,1,1\}$, but not vice versa. SubsetQ ignores duplicates, which is not desired.

$\endgroup$
2
  • $\begingroup$ I'm wondering if you can adapt the solutions from this question, which is about set subtraction where the sets can have multiple elements the same. $\endgroup$
    – march
    Nov 28, 2015 at 3:26
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$
    – Michael E2
    Nov 28, 2015 at 4:11

4 Answers 4

6
$\begingroup$

I like Counts for this:

SubmultisetQ[list1_, list2_] :=
 With[{c1 = Counts[list1], c2 = Counts[list2]},
  SubsetQ[Keys@c1, Keys@c2] &&
   AllTrue[MapThread[GreaterEqual, KeyIntersection[{c1, c2}]],
    Identity]];

SubmultisetQ[{1, 2, 1, 1}, {1, 1, 1}]
(* True *)

SubmultisetQ[{1, 2, 2, 1}, {1, 1, 1}]
(* False *)
$\endgroup$
6
$\begingroup$

Proposition

Here is a pattern-matching approach:

Attributes[oList] = Orderless;
sublistQ[{s1___}, {s2___}] := MatchQ[oList[s1], oList[s2, ___]];

Taking the examples of Pillsy:

sublistQ[{1, 2, 1, 1}, {1, 1, 1}]
(* True *)

sublistQ[{1, 2, 2, 1}, {1, 1, 1}]
(* False *)

Proposition 2 (update)

This alternative is faster (see below for updated timings):

sublist2Q[l_List, {s___}] := MatchQ[l, {OrderlessPatternSequence[s, ___]}]

Timings

The best performance amongst the solutions proposed so far will depend on the structure of the input lists. (And so does the scaling for each of them.)

As a few examples, here sublistQ and sublist2Q perform better

list = Range[10^5];
list1 = RandomSample[list, 10^5];
list2 = RandomSample[list, 10^4];

SubmultisetQ[list1, list2] // AbsoluteTiming
(* {0.69972, True} *)

MultiplicitySubsetQ[list1, list2] // AbsoluteTiming
(* {0.573459, True} *)

sublistQ[list1, list2] // AbsoluteTiming
(* {0.0750208, True} *)

sublist2Q[list1, list2] // AbsoluteTiming
(* {0.0639587, True} *)

while in what follows SubmultisetQ is the fastest

list1 = RandomInteger[10, 10^5];
list2 = RandomInteger[10, 5];

SubmultisetQ[list1, list2] // RepeatedTiming
(* {0.00025, True} *)

MultiplicitySubsetQ[list1, list2] // RepeatedTiming
(* {0.105, True} *)

sublistQ[list1, list2] // RepeatedTiming
(* {0.029, True} *)

sublist2Q[list1, list2] // RepeatedTiming
(* {0.027, True} *)
$\endgroup$
0
5
$\begingroup$

One way:

ContainsElements[set_, elements_] := Module[{labels, counts},
  {labels, counts} = Transpose@Tally[elements];
  SubsetQ[set, elements] && And @@ GreaterEqual @@@ Transpose[{labels /. Rule @@@ Tally[set], counts}]
  ]

Examples:

ContainsElements[{1, 1, 1, 1, 1}, {1, 1, 1}]
(* True *)

ContainsElements[{1, 1, 1}, {1, 1, 1, 1, 1}]
(* False *)
$\endgroup$
3
  • $\begingroup$ ContainsElements[{1, 1}, {1, 1, 2}] seems to return True. $\endgroup$ Nov 30, 2015 at 4:32
  • $\begingroup$ Adding SubsetQ[set,elements]&& in front of the Module fixed it. $\endgroup$ Nov 30, 2015 at 4:47
  • $\begingroup$ Alright, updated. $\endgroup$
    – C. E.
    Nov 30, 2015 at 9:01
3
$\begingroup$

The function CoefficientList would work for sets with only nonnegative integers:

MultiplicitySubsetQ[lset_, sset_] := 
 Module[{x}, 
  AllTrue[CoefficientList[Total[x^lset] - Total[x^sset], x], # >= 0 &]
 ]

This would work for all sets:

MultiplicitySubsetQ[lset_, sset_] := 
 Module[{x}, 
  AllTrue[List @@ (Total[x^lset] - Total[x^sset]) /. x -> 1, # >= 0 &]
 ]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.