Ask Your Question
0

Rekursive Generator which fetches a subset of elements on demand

asked 2018-01-29 16:19:21 +0100

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 flag offensive close merge delete

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 gravatar imagedan_fulea ( 2018-01-29 19:17:50 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-01-30 12:57:11 +0100

dan_fulea gravatar image

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

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2018-01-29 16:19:21 +0100

Seen: 270 times

Last updated: Jan 30 '18