# SubsetQ[] without ignoring duplicates

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.

• 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. – march Nov 28 '15 at 3:26
• 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! – Michael E2 Nov 28 '15 at 4:11

I like Counts for this:

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

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

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


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 *)

• ContainsElements[{1, 1}, {1, 1, 2}] seems to return True. – JungHwan Min Nov 30 '15 at 4:32
• Adding SubsetQ[set,elements]&& in front of the Module fixed it. – JungHwan Min Nov 30 '15 at 4:47
• Alright, updated. – C. E. Nov 30 '15 at 9:01

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} *)


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 &]
]