6
\$\begingroup\$

This code is meant to create a list of subsets of a given set which is represented as a list.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def subsets(s):
    if s == []:
        return [s]
    sets = [s]
    for i in range(0, len(s)):
        tmp_subsets = subsets(s[:i] + s[i+1:])
        for subset in tmp_subsets:
            if subset not in sets:
                sets.append(subset)
    return sets

I'm also not sure if using the set() data structure would be considered cheating in an interview context.

If there are any ideas about how to improve its performance without significantly compromising on readability I would also be open to that.

\$\endgroup\$

3 Answers 3

8
\$\begingroup\$

This is unnecessary:

if s == []:
    return [s]

You can safely remove it, the program will still work.

This step is not so great:

if subset not in sets:
    sets.append(subset)

For two reasons:

  • Checking if a list contains some items is an \$O(n)\$ operation
  • Comparing sets is not free either

A more efficient solution is to count from 0 until 1 << n, and use the bitmap of the count to decide the elements that are part of a subset.

def subsets(s):
    sets = []
    for i in range(1 << len(s)):
        subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
        sets.append(subset)
    return sets

def is_bit_set(num, bit):
    return num & (1 << bit) > 0

That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:

    cba
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

There are 8 possible subsets, and the bits represent whether an element is in the subset or not. This is the idea used by the program:

  • The outer loop goes from 0 until 2^n - 1.
  • The inner loop goes from 0 until n - 1.
  • 1 << bit is 1 shifted to the left bit times.

For example, when i = 3, that corresponds to bits 011. We loop from 0 until 2, comparing i against 001, 010, and 100. For these values, the expression i & (1 << bit) will be evaluated as 011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively. The first two are greater than 0, the last one is not.

\$\endgroup\$
6
  • \$\begingroup\$ Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part. \$\endgroup\$ Nov 20, 2016 at 22:20
  • \$\begingroup\$ @NikolasRieble I added more explanation about the bit shifting algorithm. \$\endgroup\$
    – janos
    Nov 20, 2016 at 22:45
  • \$\begingroup\$ @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :) \$\endgroup\$ Nov 21, 2016 at 6:10
  • \$\begingroup\$ @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary. \$\endgroup\$
    – Graipher
    Nov 21, 2016 at 7:31
  • \$\begingroup\$ Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable. \$\endgroup\$
    – ChatterOne
    Nov 21, 2016 at 8:20
6
\$\begingroup\$

No need to reinvent the wheel here. You can get subsets with length r as tuples of a set s by using itertools.combinations. Doing this for all possible subset lengths:

def subsets(s):
    for cardinality in range(len(s) + 1):
        yield from combinations(s, cardinality)

If you want the subsets as sets instead of tuples and within a list you can invoke the method above via:

sub_sets = [set(sub_set) for sub_set in subsets(s)]
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :) \$\endgroup\$ Nov 22, 2016 at 7:27
5
\$\begingroup\$

@janos Answer is great, but it was easier for me to think about it with one less bitwise operations.

def subsets(s):
    """
    :type s: list[]
    """
    sets = []
    for i in range(2**len(s)):
        subset = []
        for j in range(len(s)):
            if i & (1 << j) > 0:
                subset.append(s[j])
        sets.append(subset)
    return sets

Explanation:

So we know there are \$2^n\$ subsets in a set where \$n\$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):.

This gives us a range \$0 - 2^n\$ which corresponds to these binary numbers (example of a set of size 3):

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111
...
n - 1 = 0b(n-1) 

As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.

Now we just need to use these indexes to find out what should be in each set. (While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)

So we'll do a nested for loop: for j in range(len(s)):

Here we do need to do a bitwise operation: i & (1 << j) > 0 where i is the current index of the loop described earlier. j is the index of which element in the second loop we're at.

1 << j just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001, or the second 1 << 1 = 010, etc.

The & operator just makes sure the indexes match up. 000 & 101 = 0 but 100 & 101 = 100. So anytime it is greater than 0, it means we've come across an element that belongs in our set.

Let's take the set {a, b, c} and loop through our range. At 0, 0 & anything = 0, so we have the empty set.

Let's skip to i = 6: 6 & (1 << 0) > 0 returns false because in binary: 110 & 001 = 0. But the second iteration (j = 1) 6 & (1 << 1) > 0 returns true (110 & 010 = 1). And it will for the 3rd element too. Thus giving you the subset {b, c}.

The runtime of this algorithm is \$O(2^n)\$ if that isn't clear! Hope this helps!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.