0

I was wondering if there was a relatively simple way to find all subsets of list iteratively. Using recursion, this is easily done and very concise...

def partial(alist, pos, chosen):
    if pos == len(alist):
        return [chosen]
    else:
        return partial(a list, pos+1, chosen) \
               + partial(alist, pos+1, chosen + [alist[pos]])

This will return a list of lists containing all subsets of a list.

Is there a way to do something like this iteratively without it being overly complicated, or is recursion the best way? Some pseudo-code or something explaining a way to do this iteratively would be helpful. I know itertools is helpful but I would like a solution without the need for it if possible.

Saeid
  • 4,147
  • 7
  • 27
  • 43
buydadip
  • 8,890
  • 22
  • 79
  • 154
  • Just to clarify `partial([a, b, c])` creates: `[[a], [b], [c], [a,b], [a,c], [b,c], [a,b,c]]`? – shuttle87 Dec 09 '15 at 20:13
  • @shuttle87 yeah thats what it does, it also includes empty list but that's not necessary – buydadip Dec 09 '15 at 20:14
  • What are the other parameters used for here? If the only task is to generate the [power set](https://en.wikipedia.org/wiki/Power_set) this is fairly easy using itertools. – shuttle87 Dec 09 '15 at 20:17
  • @shuttle87 the other parameters are the counter, and the list of lists, so you would run it as so `partial(list, 0,[])`. – buydadip Dec 09 '15 at 20:18
  • if it is for creating powersets I'd have a look at [powerset of a given set](https://stackoverflow.com/questions/18826571/python-powerset-of-a-given-set-with-generators) - which has both the generator and linear itertools methods listed – LinkBerest Dec 09 '15 at 20:39

3 Answers3

4

As there are 2**n subsets (n is length of the list). You can create a counter from 0 to 2**(n-1). Then create a list (which is a subset) in each iteration by adding the elements who's corresponding bit is set to 1 in the counter binary form.

counter = 5
binary_form = 101
you create a subset using first and third element of the original list

counter = 7
binary_form = 111
you create a subset using first, second and third element of the original list

One could implement this like this,

result = [] 
A = [1,2,3,4]
for i in range(0,2**len(A)):
    binary = bin(i)[2:] 
    binary = '0'*(len(A)-len(binary)) + binary
    subset = [ A[i] for i,x in enumerate(binary) if x=='1' ]
    print binary,subset
    result.append(subset)
print result

Output

0000 []
0001 [4]
0010 [3]
0011 [3, 4]
0100 [2]
0101 [2, 4]
0110 [2, 3]
0111 [2, 3, 4]
1000 [1]
1001 [1, 4]
1010 [1, 3]
1011 [1, 3, 4]
1100 [1, 2]
1101 [1, 2, 4]
1110 [1, 2, 3]
1111 [1, 2, 3, 4]

But as mentioned in comments and other answers it is better not to make the binary string. If you want to check if a certain bit is set, you can shift 1 by desired amount and do a bitwise-and with that number. For example to check if the third bit is set in 423 you can do this:

number = 423
if number & 1<<3:
    print 'this bit is set'
Saeid
  • 4,147
  • 7
  • 27
  • 43
  • I like the overall idea here but I'd avoid using strings here for the indexing. – shuttle87 Dec 09 '15 at 20:32
  • I don't understand. Which part do you mean? – Saeid Dec 09 '15 at 20:34
  • This answer http://stackoverflow.com/a/34188401/296460 does something very similar to your approach but does not use any strings. – shuttle87 Dec 09 '15 at 20:35
  • Essentially the numbers are *already* binary in the computer, you just need to do bitwise operations on them to extract the information you need. By creating a string that contains the ascii characters for '0' and '1' then testing against that you are essentially creating at the minimum 8times more memory usage because each ascii character needs to be stored in 8 bits at the minimum. – shuttle87 Dec 09 '15 at 20:37
  • Yes I know and you are right. I just wanted to show what really happens and print the output of each iteration. But I totally agree with you. – Saeid Dec 09 '15 at 20:40
2

As @sudomakeinstall2 mentioned, you can use a counter from 0 to 2**(n-1) to iterate over the list, and use it as the mask to pick values from alist.

def partial(alist):
    result = []
    for i in range(2 ** len(alist)): # iterate over all results
        tmp = []
        for j in range(len(alist)):
            if (2 ** j) & i:         # use bit mask to pick the value
                tmp.append(alist[j])
        result.append(tmp)

    return result

The result may be very very large, you may want to create a generator to evaluate lazily.

With list comprehension and generator:

def partial(alist):
    for i in range(2 ** len(alist)):
        yield [alist[j] for j in range(len(alist)) if 2 ** j & i]

You can call it with

for i in partial([1, 2, 3]):
    print(i)

or

result = list(partial([1, 2, 3]))
Cychih
  • 352
  • 2
  • 14
1

Essentially building the list of subsets is the same as building the list of all combinations of sizes 1 through to length of the input. So one solution involves using itertools:

import itertools

def all_subsets(l):
    res = []
    for subset_len in range(1, len(l)+1):
        for combo in itertools.combinations(l, subset_len):
            res.append(combo)
    return res

data = [1, 2, 3, 4]
print(all_subsets(data))

see this in action here: http://ideone.com/geTdUS

The main reason I'd shy away from using recursion too much in a case such as this is because you might end up with a very large number of recursive calls and the maximum recursion depth in Python might not be deep enough. That said I'm not entirely sure how large an input size this itertools solution will work for.

shuttle87
  • 15,466
  • 11
  • 77
  • 106