# Selecting subsets of a list containing a specific element

I'm trying to generate all the subsets of a set containing a specific element.

For example, for the set {1, 2, 3, 4}, with the specific element I want inside each subset being 4, the required answer would be

{{4}, {1, 4}, {2, 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}


My current code is to do Select[Subsets[Range[n]], MemberQ[#, n] &], where for the above example we would have n=4. However, the code seems inefficient and my computer runs out memory for n>25. Is there a more efficient way to do so, or is this already the best?

NB: I will only need to work with one of the subsets at any point of time, but the Select code above doesn't seem to allow me to pick an arbitrary $i^{th}$ subset.

-

The easiest thing to do is to set aside that element before forming your Subsets, like so:

set = Range[25];
n = 9;
Timing[Append[#, n] & /@ Subsets[DeleteCases[set, n]];]
(* 14.8 s versus 47.6 s for the Select method *)


You can specify the $i^{\rm th}$ subset using the third argument to Subsets.

-
Thank you for your solution - I think it's similar in concept to that of kguler. Your Append[#,n]& /@ was just what I was looking for. – Vincent Tjeng Feb 22 '13 at 6:27

Here's another idea, piggybacking on existing Mathematica code for finding only some subsets.

subsetsWithSpecialMembers[set_, special_List, nspec_, s_] :=
Map[Join[#, special] &,
Subsets[Complement[set, special], nspec, s]];

subsetsWithSpecialMembers[set_, special_List, nspec_] :=
Map[Join[#, special] &, Subsets[Complement[set, special], nspec]];

subsetsWithSpecialMembers[set_, special_List] :=
Map[Join[#, special] &, Subsets[Complement[set, special]]];

subsetsWithSpecialMembers[Range[4], {4}] (* original request*)

subsetsWithSpecialMembers[Range[4], {4}, {2, 4}, {3}](* just the third subset of subsets
with length 2 through 4*)

-
My answer is quite similar to Xerxes but possibly a bit more general in that it permits multiple elements to be privileged. His appears somewhat faster. – Seth Chandler Feb 22 '13 at 6:01
I believe Xerxes' code can be generalized to work in a similar way to yours by modifying the DeleteCases code slightly. Thanks for the answer! – Vincent Tjeng Feb 22 '13 at 6:35

The following uses the same idea as in @Seth's answer implemented differently:

Making use of the various argument patterns Subsets accepts:

the following function joins with member each of the number subsets of Complement[list,member] with size =size:

 ClearAll[subsetsF];
subsetsF[list_, members_, size_:All, number_:All] :=
With[{list2 = (list /. Thread[members -> Sequence[]])},
Join[#, members] & /@ Subsets[list2, size, number]]


Usage examples:

  subsetsF[Range[4],  {4}] (* op's example *)
(* {{4}, {1, 4}, {2, 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}} *)

subsetsF[Range[4], {4}, {2, 3}] (* subsets containing 3 or 4 elements including 4 *)
(* {{1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}} *)

subsetsF[Range[4], {4}, {2, 3}, -2] (* "last" 2 subsets with 3 or 4 elements including 4 *)
(* {{2, 3, 4}, {1, 2, 3, 4}} *)

-
Hi @kguler, thank you for your answer. I do believe you meant subsetsF in your usage examples? Also, is it possible to generalize your solution if I want all subsets containing a set of specific elements? For instance, all subsets of Range[4] containing {3,4}. – Vincent Tjeng Feb 22 '13 at 6:31
@VincentTjeng, yes.. just corrected. – kglr Feb 22 '13 at 6:36
Thank you! Didn't mean to be pedantic about it, was slightly confused at first. – Vincent Tjeng Feb 22 '13 at 6:40