Ask Your Question
2

Subset function

asked 2018-04-16 01:46:21 +0100

amadeo_ gravatar image

updated 2018-04-16 10:09:42 +0100

slelievre gravatar image

I am new to Sage and trying to define a recursive function that returns the subsets for a given set. I get some sort of memory error for even the smallest sets and I don't know why:

def MySubsets(L):
    if L == []:
        return [[]]

    TheSubsets = MySubsets(L[1:len(L)])

    for subset in TheSubsets:
        newSubset = copy(subset)
        newSubset.append(L[0])

        TheSubsets.append(newSubset)

    return TheSubsets

...and while MySubsets([]) works, MySubsets([1]) already yields a memory error.

edit retag flag offensive close merge delete

Comments

Welcome to Ask Sage! Thank you for your question!

slelievre gravatar imageslelievre ( 2018-04-16 10:10:34 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-04-16 19:55:51 +0100

The problem is that you are looping over the list TheSubset, but your for loop is modifying TheSubset, making it larger, so the loop never ends. If you use instead for subset in copy(TheSubsets):, I think it will work.

Another option, in case you care about sets rather than lists:

sage: S = Set([1,2,3])
sage: S.subsets()
Subsets of {1, 2, 3}
sage: list(S.subsets())
[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
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-04-16 01:46:21 +0100

Seen: 364 times

Last updated: Apr 16 '18