find subsets
r_poetic
here is a quick question from a novice.
First, generate a list of subsets using Subsets or KSubsets
functions.
Ns = KSubsets[{a,b,c,d,e},3] = {{a,b,c},{a,b,d},{a,b,e},{a,c,d}, etc.}
How can one infer from that list a list of its members that contain
given elements, e.g. a list of members that contain b, or those that
contain both b and c? For illustration:
Some_function[Ns, b and c] = { {a,b,c},{b,c,d},{b,c,e}}
I keep thinking there must be a direct way to do this using Select or
some other function?
Tomas Garza
In[2]:= Select[Ns,MemberQ[#,b]&&MemberQ[#,c]&]
Out[2]= {{a,b,c},{b,c,d},{b,c,e}}
Tomas
> Date: Sat, 7 Nov 2009 06:47:11 -0500
> From: radford...@mms.gov
> Subject: find subsets
> To: math...@smc.vnet.net
Bob Hanlon
Ns = Subsets[{a, b, c, d, e}, {3}];
Needs["Combinatorica`"]
Ns == KSubsets[{a, b, c, d, e}, 3]
True
Cases[Ns, {___, b, ___}]
{{a, b, c}, {a, b, d}, {a, b, e}, {b, c, d}, {b, c, e}, {b, d, e}}
% == Cases[Ns, _?(! FreeQ[#, b] &)]
True
%% == Select[Ns, ! FreeQ[#, b] &]
True
Cases[Ns, {___, b, c, ___}]
{{a, b, c}, {b, c, d}, {b, c, e}}
% == Cases[Ns, {___, b, ___, c, ___}]
True
%% == Cases[Ns, _?(! FreeQ[#, b] && ! FreeQ[#, c] &)]
True
Bob Hanlon
---- r_poetic <radford...@mms.gov> wrote:
=============
Helen Read
> Hello,
> here is a quick question from a novice.
>
> First, generate a list of subsets using Subsets or KSubsets
> functions.
>
> Ns = KSubsets[{a,b,c,d,e},3] = {{a,b,c},{a,b,d},{a,b,e},{a,c,d}, etc.}
It's a good practice to use names that begin with a lower case letter,
to avoid conflict with the names of built-in symbols and functions.
> How can one infer from that list a list of its members that contain
> given elements, e.g. a list of members that contain b, or those that
> contain both b and c? For illustration:
>
> Some_function[Ns, b and c] = { {a,b,c},{b,c,d},{b,c,e}}
>
> I keep thinking there must be a direct way to do this using Select or
> some other function?
Select together with MemberQ will do the job. First, generate the subsets:
sets = Subsets[{a, b, c, d, e}, {3}]
This will select the ones that contain b:
Select[sets, MemberQ[#, b] &]
This will select the ones that contain both b and c:
Select[sets, (MemberQ[#, b]) && (MemberQ[#, c]) &]
And this will select the ones that contain b or c:
Select[sets, (MemberQ[#, b]) || (MemberQ[#, c]) &]
--
Helen Read
University of Vermont
Leonid Shifrin
for initial set not too large, the following function should do:
Clear[getSubsets]
getSubsets[sets_List, all_List] :=
Select[sets, Complement[all, #] === {} &];
getSubsets[sets_List, all_List, {}] := getSubsets[sets, all];
getSubsets[sets_List, all_List, oneOf_List] :=
Select[getSubsets[sets, all], MemberQ[#, Alternatives @@ oneOf] &];
It will find all sublists which contain *all* of the elements in <all>
argument and *at least one* of the elements of <oneOf> argument (which can
be omitted altogether). For example:
In[1] :=
ClearAll[a, b, c, d, e, f, g, h];
sets = Subsets[{a, b, c, d, e, f, g, h}, {6}];
In[2]:=
getSubsets[sets,{a,b,g},{}]
Out[2]:=
{{a,b,c,d,e,g},{a,b,c,d,f,g},{a,b,c,d,g,h},{a,b,c,e,f,g},{a,b,c,e,g,h},{a,b,c,f,g,h},{a,b,d,e,f,g},{a,b,d,e,g,h},{a,b,d,f,g,h},{a,b,e,f,g,h}}
In[3]:=
getSubsets[sets,{a,b},{c,d}]
Out[3]=
{{a,b,c,d,e,f},{a,b,c,d,e,g},{a,b,c,d,e,h},{a,b,c,d,f,g},{a,b,c,d,f,h},{a,b,c,d,g,h},{a,b,c,e,f,g},{a,b,c,e,f,h},{a,b,c,e,g,h},{a,b,c,f,g,h},{a,b,d,e,f,g},{a,b,d,e,f,h},{a,b,d,e,g,h},{a,b,d,f,g,h}}
If the initial set is large, the above approach may turn inefficient due to
a vary large number of elements in the initial list of subsets. You may want
then to take the requirement of presence of certain elements into account
already at the point when you generate the subsets.
Regards,
Leonid
On Sat, Nov 7, 2009 at 3:47 AM, r_poetic <radford...@mms.gov> wrote:
> Hello,
> here is a quick question from a novice.
>
> First, generate a list of subsets using Subsets or KSubsets
> functions.
>
> Ns = KSubsets[{a,b,c,d,e},3] = {{a,b,c},{a,b,d},{a,b,e},{a,c,d}, etc.}
>
Bill Rowe
>First, generate a list of subsets using Subsets or KSubsets
>functions.
>Ns = KSubsets[{a,b,c,d,e},3] = {{a,b,c},{a,b,d},{a,b,e},{a,c,d},
>etc.}
>How can one infer from that list a list of its members that contain
>given elements, e.g. a list of members that contain b, or those that
>contain both b and c? For illustration:
>Some_function[Ns, b and c] = { {a,b,c},{b,c,d},{b,c,e}}
>I keep thinking there must be a direct way to do this using Select
>or some other function?
In[4]:= Cases[
Subsets[{a, b, c, d, e},
3], _?(Length[Intersection[#, {c, b}]] == 2 &)]
Out[4]= {{b,c},{a,b,c},{b,c,d},{b,c,e}}
rs_poetic
RS