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.
$\begingroup$
$\endgroup$
2
asked Nov 28, 2015 at 2:54
-
$\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$– marchCommented 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 E2Commented Nov 28, 2015 at 4:11
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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 *)
$\begingroup$
$\endgroup$
0
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} *)
$\begingroup$
$\endgroup$
3
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 *)
-
$\begingroup$
ContainsElements[{1, 1}, {1, 1, 2}]seems to returnTrue. $\endgroup$ Commented Nov 30, 2015 at 4:32 -
$\begingroup$ Adding
SubsetQ[set,elements]&&in front of theModulefixed it. $\endgroup$ Commented Nov 30, 2015 at 4:47 -
$\begingroup$
$\endgroup$
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 &]
]
answered Nov 30, 2015 at 4:16
$\begingroup$
$\endgroup$
Using MultisetIntersection by Robert B. Nachbar (Wolfram Solutions)
MultisetIntersection = ResourceFunction["MultisetIntersection"];
a = {{1, 2, 1, 1}, {1, 1, 1}};
MultisetIntersection @@ a == Last[a]
True
b = {{1, 2, 2, 1}, {1, 1, 1}};
MultisetIntersection @@ b == Last[b]
False
