# Rekursive Generator which fetches a subset of elements on demand

i have following Task to solve; write a generator which outputs a Set (M) of Sets(S) with subsets of M from S \ {s] and M and {s} .. sounds weird.

what i wrote is:

def getSubsets(S):
if(sage.sets.set.is_Set(S)):
s=Set(S.subsets())
for sub in s:
yield [sub]
else:
if(S.is_empty() == false):
yield [S]
else:
yield []


with following test, i can mySet.next() fetch a Set from the Pool of Sets.

var('a','b','c','d')
a=Set([3,4])
b=Set([a,c,d])
d=Set([])
mySet = Set([a,b,1,2])
print(mySet)
myGen = getSubsets(mySet)


Now i have a Problem, rewriting that as recursive function. Is that even possible? Please dont send in "perfect solutions", i want to learn how to solve that puzzle by myself.

Thank you!

edit retag close merge delete

• the input
• the output

for the "generator". Do we have to implement the subsets of a given set recursively? The code should deliver the list / (power) set $\mathcal P(S)$ of the subsets of a given set $S$, or should only give an iterator for it? (If this is the case, than the problem - translated in terms of characteristic functions - wants to construct ${0,1}^{n+1}$ as ${0,1}\times {0,1}^n$. Try to do this first.

( 2018-01-29 12:17:50 -0500 )edit

Sort by » oldest newest most voted

I am not quite sure what should be implemented, i think it is the following recursive function:

def my_subsets(S):
if len(S) == 0:
return Set( [ Set([]) ] )
s = S[0]
T = S.difference( Set( [s] ) )
PT = my_subsets(T)
return PT + Set( [ Set([s]) + A for A in PT ] )


For instance:

for A in my_subsets( Set( [1,2,3,'abc'] ) ):
print A


which delivers:

{'abc'}
{1, 2}
{}
{2, 'abc'}
{1, 3}
{1, 2, 'abc'}
{1, 3, 'abc'}
{3}
{2}
{2, 3}
{1}
{1, 'abc'}
{2, 3, 'abc'}
{1, 2, 3, 'abc'}
{1, 2, 3}
{3, 'abc'}


where

sage: len( my_subsets( Set( [1,2,3,'abc'] ) ) )
16


(The shown order the elements is completely random, as one may expect. If the order is an issue, then one should use "unique" lists...)

more