Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I have a set, S, and I take Subsets[S] (the power set of S). For example:

S={a,b,c}
Subsets[S]={{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

How can I make a list which takes only sets which have an element of a subset, but not the whole set. Ideally, using the example above, something like this:

f[Subsets[S],a]={{a},{a,b},{a,c}}

Further, say I have a set of subsets. Using the above example:

L={{a},{b}}

How can I choose the elements from Subsets[S] so that any of the elements of L are subsets, but not including the whole set. Again, using the above:

g[Subsets[S],L]={{a},{b},{a,b},{a,c},{b,c}}

Ideally, g could be generalized for any power set and set of subsets.

Any help would be greatly appreciated, thank you.

share|improve this question
up vote 3 down vote accepted

This is my attempt to cover the generalized case that you describe. I went ahead and made it even a little bit more general, as the tests will show.

Solution:

SelectSubsets[S_, el : Except[_List]] := SelectSubsets[S, {el}]
SelectSubsets[S_, lists : {{__} ..}] := SelectSubsets[S, #] & /@ lists
SelectSubsets[S_, list_] := Cases[Subsets[S], Except[S,
   Prepend[___]@Append[___]@Riffle[ConstantArray[Alternatives @@ list, Length@list], ___]
   ]]

Tests:

S = {a, b, c, d};
SelectSubsets[S, a]

{{a}, {a, b}, {a, c}, {a, d}, {a, b, c}, {a, b, d}, {a, c, d}}

SelectSubsets[S, {a, b}]

{{a, b}, {a, b, c}, {a, b, d}}

SelectSubsets[S, {{a}, {b}}]

{{{a}, {a, b}, {a, c}, {a, d}, {a, b, c}, {a, b, d}, {a, c, d}}, {{b}, {a, b}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {b, c, d}}}

Union @@ SelectSubsets[S, {{a}, {b}}]

{{a}, {b}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}}

SelectSubsets[S, {{a, b}, {b, d}}]

{{{a, b}, {a, b, c}, {a, b, d}}, {{b, d}, {a, b, d}, {b, c, d}}}

Explanation

SelectSubsets is implemented in terms of Cases[list, form] which compares every element in list to the pattern form in order to determine if it should be included in the result.

Except is used in the pattern to remove the full set from the list:

S = {a, b, c};
Cases[Subsets[S], Except[S]]

{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}}

The heart of the solution is this pattern:

Prepend[___]@Append[___]@Riffle[ConstantArray[Alternatives @@ list, Length@list], ___]

For example if list is {a, b} then this results in

{___, a|b, ___, a|b, ___}

and if list is {a, b, c} it evaluates to

{___, a|b|c, ___, a|b|c, ___, a|b|c, ___}

So, this pattern will find every subset that includes a, b, and c.

The more complex inputs can be handled using the pattern described above. You will find that the two first definitions of SelectSubsets are just ways to do what they are supposed to do in terms of this pattern.

share|improve this answer
    
Thank you so much, this is exactly what I was looking for! – jix816 Jan 19 at 0:45
    
Instead of Except[S,...], what if I wanted to exclude all subsets which contained a specific set. Also, if I wanted to exclude sets which weren't the union of elements of the list of lists. For example: S={1,2,3,4,a,b,c,d}, exclude.sets.containing={1,2,3,4}, L={{a,1,4},{b,1,2},{c,2,3},{d,3,4}}. Then f[S,N,L]=Union[L,{{a,b,1,2,4},{a,d,1,3,4},{b,c,1,2,3},{c,d,2,3,4}}] This may be an entirely different question, perhaps I should make another post? I am unsure of the protocol. – jix816 Jan 19 at 1:19
    
@jix816 Start by reading the documentation for Except, could it be as simple as moving what is now the second argument to the first argument of Except? I think it would be better if you asked at least the second question as a new question, as you suggested, but make sure to mention this question. – C. E. Jan 19 at 1:34
    
I will do just that. Thank you very much for your assistance! – jix816 Jan 19 at 1:40

To not generate all subsets we can do something like:

ClearAll[sel]
sel[el_, set_] := Flatten[#, 1] & /@ Most @ Tuples[{
     Rest @ Subsets[el], 
     Subsets @ DeleteCases[set, Alternatives @@ el]
}]

sel[{a}, {a, b, c}]
{{a}, {a, b}, {a, c}}
sel[{a, b}, {a, b, c}]
{{a}, {a, c}, {b}, {b, c}, {a, b}}
share|improve this answer
    
Thank you for your help! – jix816 Jan 19 at 0:04

You should use SubsetQ[list1,list2] which is True exactly if list2 is a subset of list1. So define

SubsetLQ[list1_,listoflists_]:=And@@(SubsetQ[list1,#]&/@listoflists)

This should give you True exactly if all elements of listoflists are a subset of list1. Then use

Select[Subsets[S],SubsetLQ[#,L]&&Length@#<Length@S&]

This should work, provided I understood correctly what you are looking for

share|improve this answer
    
Thank you so much for your help! – jix816 Jan 19 at 0:03
Select[Subsets[{a, b, c}], MemberQ[#, a] && Length@# < 3 &]

{{a}, {a, b}, {a, c}}

Select[Subsets[{a, b, c}], MemberQ[#, a | b] && Length@# < 3 &]

{{a}, {b}, {a, b}, {a, c}, {b, c}}

share|improve this answer
    
I really appreciate your help! – jix816 Jan 19 at 0:04

Update with more general solution that makes at most one extra subset and works when items are not in set.

h[set_List, items_List] :=
 With[{comp = Complement[set, items]},
  Select[Length@# != Length@comp + Length@items &]@
   Flatten[Outer[Flatten@*Join, Subsets[items, {1, Length@items}], Subsets[comp], 1], 1]
  ]

h[{a, b, c}, {a}]
(* {{a}, {a, b}, {a, c}} *)

h[{a, b, c}, {a, b}]
(* {{a}, {a, c}, {b}, {b, c}, {a, b}} *)

h[{a, b, c}, {f}]
(* {{f}, {f, a}, {f, b}, {f, c}, {f, a, b}, {f, a, c}, {f, b, c}} *)

Original post

ContainsAny with Select (twice).

g[set_List, items_List] := 
 Select[set != # &]@Select[ContainsAny[items]]@Subsets[set]

s = {a, b, c}; t = {a};
g[s, t]

(* {{a}, {a, b}, {a, c}} *)

t = {{a}, {b}};
g[s, Flatten@t]

(* {{a}, {b}, {a, b}, {a, c}, {b, c}} *)

Hope this helps.

share|improve this answer
    
This helped very much. Thank you! – jix816 Jan 19 at 0:05

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.