Computing subsets from a set?

[OLer94]

Hello everyone, Im very new to python so I am having a hard time with it. I am trying to input a set 's' and have it spit out 'result' which would be a list of all computed subsets of 's'.

I wrote the following code but its not working. When I make a set (call it b) and run subsets(b), I get a bunch of errors. What am I missing here?

def subsets(s):
	result = [set()]
	for xi in s:
		newsubsets=[]
		for subset in result:
			newsubsets.copy(subsets)
			newsubsets.add(xi)
			newsubsets.append(newsubsets)
			result.extend(newsubsets)
	return result

[jrcagle]

Well, Python and I were both confused by this line:

newsubsets.copy(subsets)

Did you intend for newsubsets to become a copy of subsets? If so, then you want

newsubsets = subsets[:]

But I question the wisdom of clobbering newsubsets every time you go through the inner loop. Seems like that would destroy a lot of hard work.

Did you mean something else?

Jeff

[vegaseat]

Looks to me that you are using operations for sets like copy() and add() with lists.

[jrcagle]

For what it's worth, my implemenation of this function used recursion.

[OLer94]

Well, Python and I were both confused by this line:

newsubsets.copy(subsets)

Did you intend for newsubsets to become a copy of subsets? If so, then you want

newsubsets = subsets[:]

Yes, that way I can keep adding new susbets as the program loops.

But I question the wisdom of clobbering newsubsets every time you go through the inner loop. Seems like that would destroy a lot of hard work.

Did you mean something else?

Jeff

Is there a better way? Again, Im new at this.

I basically want to say b=[1,2,3] and then write a function subset(b) that will yield ([1], [2], [3], [1,2], [2,3], [1,3])

[jrcagle]

And don't forget [] and [1,2,3], which are also subsets of b. P(b) = subsets(b) should have 2^len(b) elements.

Here's a recursive way to think about it:

if:
    b is empty, then P(b) = [].
else:  #b is not empty 
    form all subsets x of size len(b)-1.  
    Then P(b) = the union of P(x) for all x, union b.

Example: if b = [1,2,3], then P(b) = P([1,2]) U P([1,3]) U P([2,3]) U [1,2,3].

See if you can get some Python out of that.

Jeff

[OLer94]

Hey everyone,

I just wanted to show you my revised program. Unfortuantely, I have to use a loop to generate this set, so I couldnt revamp my approach. So here was the following:

p=set([1,2,3,3,3,4,4,7,5,8])
def subsets(s):
    result = [set()]
    for xi in s:
        finalsubsets=[]
        for subset in result:
            newsubset=s.copy()
            newsubset.add(xi)
            finalsubsets.append(newsubset)
    return result
    print result

subsets(p)
[set([]), 1, 2, 3, 4, 5, 7, 8]

It still didnt give me what I thought I was going to get. Do you have any suggestions?

[jrcagle]

This is not the cleanest, but I'm not thinking clearly at the moment:

def subsets(x):
    if x == []:
        return [[]]
    else:
        s = [x]
        for elem in x:
            tmp = x[:]
            tmp.remove(elem)
            new_sub = subsets(tmp)
            for y in new_sub:  # <-- can't just make it a set(), because lists aren't hashable.
                if y not in s:
                    s.append(y)
        return s
>>> s = [1,2,3]
>>> subsets(s)
[[1, 2, 3], [2, 3], [3], [], [2], [1, 3], [1], [1, 2]]

Jeff

[notagoodchoice]

A recursive approach isn't the best one here. Subset creation can be done more efficient in an iterative way. The following code is approx. 2x faster on a set of 3 elements and even 22x faster on a set of 6 elements and so on (according to timeit):

def subsets_i(s):
    subsets = []
    n_elems = len(s)
    n_subsets = 2**len(s)
    for i in range(0,n_subsets):
        sub = []
        for j in range(0,n_elems):
            if (i >> j & 1):
                sub.append(s[j])
        subsets.append(sub)
    return subsets

The idea here is that a set with n elements has n^2 subsets and that each subset #i with i = 0 .. (n^2 - 1) is described by the binary representation of the number i :

i =  0 -> 00000 -> subsets[0] = []
...
i = 20 -> 10100 -> subsets[20] = [s[2], s[4]]
i = 21 -> 10101 -> subsets[21] = [s[0], s[2], s[4]]
...

[notagoodchoice]

The idea here is that a set with n elements has n^2 subsets and that each subset #i with i = 0 .. (n^2 - 1) is described by the binary representation of the number i :

.. oops, it's 2^n and not n^2.

[woooee]

This thread is almost 2 years old.