0

Assume we have a set of N items say, S = {t1, t2, t3}. I would like to produce all the possible subsets of S given the restriction that t1 must appear in every set. Therefore, all possible subsets of S are {t1}, {t1,t2}, {t1,t3}, and {t1,t2,t3}. How can I write a recursive function that takes two sets {t1} and {t2,t3} and returns the subsets listed above.

Also if I had 100s of subsets such as S, storage of all subsets becomes a problem. My program goes in iterations and at every iteration I only need to manipulate one subset from each set. Is there I way I can produce the subsets of a set in steps rather than all at once? i.e. every time I call next(S), I get a new subset.

Note I'm coding in C.

NewToAndroid
  • 581
  • 7
  • 25
  • 2
    "I'm coding in C." - Not that I can see. What have you got so far? – WhozCraig Mar 06 '14 at 05:38
  • 2
    I'm voting to close, but search on "C power set". You are building a subset of a "power set". Given a restriction, you don't need to make a recursive call on a subset that will never qualify. For instance: http://rosettacode.org/wiki/Power_set#C – Alex Reynolds Mar 06 '14 at 05:42
  • I have an iterative function that first produces the minimum set of items i.e. {t1}. The given {t1} it produces all sets of size 2 i.e. {t1,t2} and {t1,t3}. Finally, it just produces the superset which is {t1,t2,t3}. – NewToAndroid Mar 06 '14 at 05:43
  • 3
    This question appears to be off-topic because the code in question is invisible. – devnull Mar 06 '14 at 05:44
  • I am unsure about how to express the above logic as a recursive function. – NewToAndroid Mar 06 '14 at 05:44
  • @devnull I respectfully disagree with the close vote - the question may have too many parts, but OP is asking how to implement a specific algorithm which seems well defined. – Hooked Mar 06 '14 at 05:51
  • @NewToAndroid You should really break up the other questions into parts - ask _one_ question at a time. There are many ways to have a function save its "state" so you can call it `next()`, this are nicely done with C++ and classes, but quite possible with C as well. A nice STL based powerset of strings, for example, is here http://stackoverflow.com/a/2506186/249341 – Hooked Mar 06 '14 at 05:54

1 Answers1

2

Your "restriction" amounts to the following

  • Remove all the elements from S that must appear in the final sets. Call the remaining set S` and the removed elements B.
  • Produce the powerset of S` taking the union with B for each item to add in the required elements.

The powerset is a standard recursive function and outside the scope of your question. Indeed, there are many examples of how to do so on Stack Overflow.

Hooked
  • 84,485
  • 43
  • 192
  • 261