Bitmasks and Generating Subsets Recursively

General Questions
#1

Hello all,

I have been working on “Complete Search with Recursion” in Bronze.

I am having trouble understanding it though.

Note I do use python (and this is contributing to my confusion, as the resources like the textbook are a lot less helpful if you don’t know what the programs mean (but all I can do in C++ is std::cin, std::cout and assign integer variables :stuck_out_tongue: )).

Anyway, so with generating subsets recursively: I understood what they did with the apple problem. Essentially at every new index of the list with the apple weights, they plug it back into the code until finally they have tested all the possibilities, and then at each step find the minimum.

But I can’t figure out how you would recursively make subsets of an array in python.

I know at each index of the given array, you would decide whether or not to include it. Here’s my attempt though:

def func(subList, k, setList): #For each k decide whether or not to include it
    if k == len(subList):
        return setList
    else:
        setList.append([k, func(subList, k+1, setList)])
        setList.append(func(subList, k+1, setList))

print(func([1,2,3], 0,[]))

This doesn’t work though. I think I’m having some trouble wrapping my head around recursion.

As for bitmasks… I don’t understand them at all…

Can someone please explain what they are doing there?

In the program shown, it loops through n, which means that the nth bit is turned on or something??? And then the & operator returns what value? Just any value? It says “positive value.”

I really don’t understand these :frowning: .

Thank you all for taking the time to read this long post. I want to make sure I understand this stuff. Sorry if I’m being stupid or something too :wink: .

Thanks a lot!

#2

I think a bitwise solution is somewhat (?) simpler to understand.
Say we had a list [0, 5, 6, 7]- as we can see, its length is 4.

Now we iterate through all numbers from [0, 2^4) and convert them to their binary representations as follows:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

(apologies for the wall of text).
But if you’ll look closely at the 1’s and 0’s, you can see that this can be used to generate every single subset! Take for example 1001- from its representation, we can see that in this subset we include the first and last element, and exclude the others. Thus, we can code up a function as follows (try coding it out yourself though first!)

def subsets(arr: list):
     all_subs = []
     for i in range(1 << len(arr)):
         bin_rep = bin(i)[2:].zfill(len(arr))
         this_sub = [arr[i] for i in range(len(arr)) if int(bin_rep[i])]
         all_subs.append(this_sub)
     return all_subs

Of course, in the end you could just use python’s stdlib to generate all subsets (as explained here), but I assume you wanted to learn the methodology behind generating the subsets.

#3

Wow, thank you so much! That helped a ton – especially the visual of the different binary numbers, which allowed me to see what it meant by turning on a particular bit. Thanks again!

#4

I’m late to the thread, but here’s something relevant that I think may help:
https://sendtoaryansh.gitbook.io/informatics-notes/misc-tricks/bitmask-subsets

#5

This might help, this can iterates through the subsets of a binary value in O(3^n). i is the binary value here. Might this be what you wanted?

for (int j=i;j;j=(j-1)&i) {
#6

How did you get that complexity? Did you mean O(2^n) instead?

#7

This technique can skip all non-subset circumstances. For bitmask dp, you might want to find the subset for subsets. Using this instead of brute force, you result O(3^n).

The reason for the complexity if because there are C^x_n ways to select a x size subset. With a x size subset, there are 2^x subsets. So the total amount of subset of subsets will be:

\sum_{x=1}^{n} C^x_n \times 2^x = (1+2)^n = O(3^n)
#8

An O(3^n) complexity is too slow for most bitmask DP problems though…

#9

Wait so if you had three choices instead of two, would you do a similar thing in O(3^N) using base three?

#10

What do you mean by 3 choices?

#11

@KarL05 is saying that if you need to iterate over subsets of subsets, you can use that for loop to do it in O(3^n) time.

Original question is only asking about iterating over subsets, which is just O(2^n) and can be done either iteratively or recursively.

1 Like