Re: find subsets
- To: mathgroup at smc.vnet.net
- Subject: [mg104738] Re: [mg104694] find subsets
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Sun, 8 Nov 2009 06:47:46 -0500 (EST)
- References: <200911071147.GAA09918@smc.vnet.net>
Hi,
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.schantz at 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.}
>
> 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?
>
>
- References:
- find subsets
- From: r_poetic <radford.schantz@mms.gov>
- find subsets