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!

Comments

Please make clear what are

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.

dan_fulea ( 7 years ago )

add a comment

answered 7 years ago

dan_fulea
5650 ●5 ●44 ●97

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...)

link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Rekursive Generator which fetches a subset of elements on demand

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

Rekursive Generator which fetches a subset of elements on demand savecancel

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

Rekursive Generator which fetches a subset of elements on demand