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

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

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

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

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

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

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?

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

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

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.

This thread is almost 2 years old.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.