-1

I am trying to figure out how to do this in Python:

Print out all subsets of any given set.

For example: [1,2]

So the answer is by hand the following:

[]
[2]
[1]
[1,2]

I realized that the total number of solutions would be 2(exp)n, where n is the number of elements in the list.

So for example, if the list is [1,3,4], then the total number of subsets would be 2(exp)3 = 8.

I also realized that if I got the binary bit representation of the list above, the following appears:

So for example: [1,2]

00 : []
01 : [2]
10 : [1]
11 : [1,2]

Each position of the bit that contains a 1, that is the position of the subset when indexing it to the original set [1,2]. eg binary 01 = get index at position 1 of the original set [1,2] which would be [2].

Binary 11, means get index positions 0 and 1 from the original set [1,2] which gives an answer of [1,2], etc.

How can I code this, the code I have is so messy, is there a easy way to map this?

Grant Miller
  • 27,532
  • 16
  • 147
  • 165
fynx
  • 41
  • 5
  • Welcome to Stack Overflow! Please take the tour and read through the help center, in particular how to ask. Your best bet here is to do your research, search for related topics on SO, and give it a go. After doing more research and searching, post a Minimal, Complete, and Verifiable example of your attempt and say specifically where you're stuck, which can help you get better answers! – Jonathan Gagne Oct 05 '18 at 03:12
  • Perhaps this might be helpful: https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements – berkelem Oct 05 '18 at 03:19
  • have a look at the [itertools recipes](https://docs.python.org/3/library/itertools.html#itertools-recipes): `def powerset(iterable):` - it creates all of your sets as tuples. maybe you can work from there – Patrick Artner Oct 06 '18 at 13:42

1 Answers1

0

You can use a loop that iterates through all the binary combinations and a nested loop that tests each bit of the counter to decide whether or not to add the list element of the corresponding index to the output list:

def combinations(l):
    for i in range(1 << len(l)):
        c = []
        for b in range(len(l)):
            if i & (1 << (len(l) - b - 1)):
                c.append(l[b])
        yield c

or with list comprehension:

def combinations(l):
    return [[l[b] for b in range(len(l)) if i & (1 << (len(l) - b - 1))] for i in range(1 << len(l))]

so that:

list(combinations([1, 2])))

would return:

[[], [2], [1], [1, 2]]

and:

list(combinations([1, 3, 4]))

would return:

[[], [4], [3], [3, 4], [1], [1, 4], [1, 3], [1, 3, 4]]
blhsing
  • 91,368
  • 6
  • 71
  • 106
  • Thank you for your answer, can you explain what this line does exactly?: for i in range(1 << len(l)): ( Are they both l,s or 1's? Also why are you minusing the letter l and letter b in this statement: if i & (1 << (len(l) - b - 1)): Thx in advanced – fynx Oct 05 '18 at 17:40
  • You're welcome. By "this line" are you talking about list comprehension? It's just a way to write my first code example more concisely. You can read more about it [here](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions). – blhsing Oct 05 '18 at 17:43
  • oh no, I do understand list compreehension, I just don't understand why you are &'ing all binary numbers from 0..4 ( in case of 2 elements in l ) with len(l)-b-1. This line specifically: if i & (1 << (len(l) - b - 1)): Sorry I am a little slow... – fynx Oct 05 '18 at 18:47