3
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Feb 22, 2013 at 6:27
5
$\begingroup$

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*)
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Feb 22, 2013 at 6:01
  • $\begingroup$ 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! $\endgroup$ Commented Feb 22, 2013 at 6:35
1
$\begingroup$

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}} *)
$\endgroup$
3
  • $\begingroup$ 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}. $\endgroup$ Commented Feb 22, 2013 at 6:31
  • $\begingroup$ @VincentTjeng, yes.. just corrected. $\endgroup$
    – kglr
    Commented Feb 22, 2013 at 6:36
  • $\begingroup$ Thank you! Didn't mean to be pedantic about it, was slightly confused at first. $\endgroup$ Commented Feb 22, 2013 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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