art-hack's blog

By art-hack, 6 weeks ago, In English

Hi Everyone, I encountered this subproblem in a problem.

Suppose we are given an array of integers of size N and want to generate subsets of size K from it. I used this simple backtracking approach to generate the combinations of size K.

Backtracking Code

I was wondering if there is a possible approach to do this by using bits, a simple approach is generating all subsets and processing only the ones that have size K, but in this, we have to generate all 2N subsets.

Bits Solution

Is there a way to do this using bits without generating all the possible subsets?.

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

One nice way to do this is to create a vector of $$$n-k$$$ 0's followed by $$$k$$$ 1's. Use std::next_permutation to iterate over all combinations.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually this is really a very nice way, and pretty sure much less coding.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Indeed, a really nice solution. I didn't know that next_permutation takes care of duplicates as well, I thought that it will generate duplicates. I will look into how it actually works.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use Pascal's recursion. Go concatenating the string.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I suggest using std::next_permutation or std::prev_permutation for better complexity $$$O(\binom{n}{k})$$$

Sameple code
  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There is an error in the sample code, in the second line it should be p[N-i-1] = 1;. Instead of generating the first subset, it is creating the last one.

»
6 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Kactl has really short iterative code for this in the "10.5.1 Bit Hacks" section, with the extremely nice properties that the bitsets are generated in increasing order and no other bitsets are generated; here's roughly what it is:

int mask = (1 << k) - 1, r, c;
while(mask <= (1 << n) - (1 << (n-k))) {
    // Code here
    c = mask & -mask, r = mask+c, mask = r | (((r ^ mask) >> 2)/c);
}

The loop bounds I've written only work for $$$n \leq 30$$$ (or 62 for long longs). It's a really good exercise in bit operations to think about why this works.

Note: if you are adapting this code to long longs, make sure you change things like (1 << k) to (1LL << k).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is exactly what I was looking for and it looks like that the complexity is even better than the solution that Monogon suggested, as worst-case complexity for next_permutation is O(n). I will now try to think about why it works.

  • »
    »
    4 days ago, # ^ |
    Rev. 7   Vote: I like it +18 Vote: I do not like it

    In case you need to find previous subset instead of next subset, you can you a trick to get the inverse function: prev = ~next(~mask), next = ~prev(~mask)

    Generating next subset
    Generating prev subset

    Moreover, if you want to get the kth previous or kth next subset, you can use lexicographical dynamic programming for it.

    Here I use mask of long long, you can change to bitset<> to store larger but it will be a bit complicated

    Simple Implementation
    Full implementation (with detail comment)
    • »
      »
      »
      4 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In case guys interesting, there are some other effecient or non-effecient way to find it. (Sorry ! here I only provides implementations and not describe how these function works perfectly)

      Implementation 1 - O(n log n)
      Implementation 2
      Implementation 3
      Implementation 4
      Implementation 5