Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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*)
share|improve this answer
    
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:

enter image description here

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}} *)
share|improve this answer
    
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. –  kguler 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.