Power set generated by bits

Question

I have this code which generates power set of an array of size 4 (number is just example, less combinations to write...).

#define ARRAY_SIZE 4


unsigned int i, j, bits, i_max = 1U << ARRAY_SIZE;
int array[ARRAY_SIZE];

for (i = 0; i < i_max ; ++i) {
    for (bits = i, j = 0; bits; bits >>= 1, ++j) {
        if (bits & 1)
            printf("%d", array[j]);
    }
}

Output:

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}
{4}
{1, 4}
{2, 4}
{1, 2, 4}
{3, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}

I need that output to be like this one:

{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}

So it has to be ordered like that. I can't do that ordering after that algorithm ends, I have to use every combination in every iteration, so It has to generate that combinations already ordered. Can someone help me out? I think I was thinking about everything...

EDIT: That final output should be without empty set, but it's not priority.

Howlett

Did you mean to leave out the empty set in the second case? Mathematically speaking, it is a perfectly valid member of the power set. – Nonpareil

I meant it, just forgot to mention it, sorry. Thx. – Howlett

Such an existential question must of course be answered with 42 lines of code (see my answer) ;-) – Wolves

Answer 1

Here's a version that goes down to the metal with bit-twiddling. It uses a modified version of the famous Hackers' Delight snoob() function that generates the next greater subset with the Same Number Of One Bits. See the Chess Programming Wiki (a source of many such bit-twiddling routines).

#include <cstdint>
#include <iostream>

using U64 = uint64_t;

// print bit indices of x
void setPrint(U64 x)
{
    std::cout << "{ ";
    for(auto i = 1; x; x >>= 1, ++i)
        if (x & 1) std::cout << i << ", ";
    std::cout << "}\n";
}

// get next greater subset of set with 
// Same Number Of One Bits
U64 snoob (U64 sub, U64 set) {
   U64 tmp = sub-1;
   U64 rip = set & (tmp + (sub & (0-sub)) - set);
   for(sub = (tmp & sub) ^ rip; sub &= sub-1; rip ^= tmp, set ^= tmp)
       tmp = set & (0-set);
   return rip;
}

void generatePowerSet(unsigned n)
{
    auto set = (1ULL << n) - 1;                 // n bits
    for (unsigned i = 0; i < n+1; ++i) {
        auto sub = (1ULL << i) - 1;             // i bits
        U64 x = sub; U64 y; 
        do {            
            setPrint(x);
            y = snoob(x, set);                  // get next subset
            x = y;
        } while ((y > sub));
    }
}

int main()
{
    generatePowerSet(4);    
}

Live Example with output in lexicographic order (bonus feature)

{ }
{ 1, }
{ 2, }
{ 3, }
{ 4, }
{ 1, 2, }
{ 1, 3, }
{ 2, 3, }
{ 1, 4, }
{ 2, 4, }
{ 3, 4, }
{ 1, 2, 3, }
{ 1, 2, 4, }
{ 1, 3, 4, }
{ 2, 3, 4, }
{ 1, 2, 3, 4, }

Wolves

Well that's nice solution :) – Howlett

tnx, glad to have been of help! – Wolves

Answer 2

Write a function to generate all items of a fixed size. Note that the first such item is 1,..,k while the last is (n-k+1),..,n. This is very simple, you basically have to reimplement basic counting: you increment the last "digit", until you reach n. Then you reset to 1 and continue in the same fashion to its left.

Then just have k run from 1 (0) to n.

Here is one proposal for the internal algorithm. It's rather ugly, though.

void out(std::vector<int> const& item) {
  char del = '{';
  for (auto it = item.begin(); it != item.end(); ++it) {
    std::cout << del << *it;
    del = ',';
  }
  std::cout << "}\n";
}

bool ascending(std::vector<int> const& item) {
  int last = 0;
  for (auto it = item.begin(); it != item.end(); ++it) {
    if (*it <= last)
      return false;
    last = *it;
  }
  return true;
}

void allk(int k, int n) {
  std::vector<int> item;
  item.reserve(k+1);
  for (int i = 1; i <= k; i++)
    item.push_back(i);
  bool valid = true;
  while (valid) {
    out(item);
    do {
      valid = false;
      for (auto it = item.rbegin(); it != item.rend(); ++it) {
        if (*it == n) {
          *it = 1;
        } else {
          ++*it;
          valid = true;
          break;
        }
      }
    } while (valid && !ascending(item));
  }
}

Marieann

This generates the values if the original set is {1, ..., n}. Otherwise, if the original set has n elements, this generates 1-based indexes into that set. (Remember to -1 if you are using a 0-based container; very likely in C++). – Nonpareil

@BoBTFish: Duplicates are not entirely trivial. I'm thinking about a simple rule to eliminate those. – Marieann

Answer 3

• I started with a simple recursive permutation generator.
• Added a length parameter and, when the length reaches 0, instead of permuting further, just print the string we have so far.
• Added a position where we must continue picking characters from.

The code:

(I know some people don't like raw arrays / pointers, but it's so much easier to get great performance for this problem with that as opposed to pretty containers)

void powerSet(char *arr, int arrLen, int pos, int startPos, int length)
{
   if (length == 0)
      printf("%.*s\n", pos, arr);
   else
      for (int i = startPos; i < arrLen; i++)
      {
         std::swap(arr[pos], arr[i]);
         powerSet(arr, arrLen, pos+1, i+1, length - 1);
         std::swap(arr[pos], arr[i]);
      }
}

And the calling function:

void powerSet(char *arr, int arrLen)
{
    for (int i = 1; i <= arrLen; i++)
      powerSet(arr, 4, 0, 0, i);
}

powerSet("1234", 4) prints:

1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234

Test.

Hazy

I was thinking of a similar thing first, but OP wants all sets, so AC = CA. – Marieann

Answer 4

Use a buffer array and then sort it using qsort ?

I used a i_max*5 elements array : 4 unsigned int for the values (0 means empty, 1 to 4 otherwise) and a final unsigned int for the subset length. Then, you just have to roll with your custom comparator. If you want to a more streamlined algorithm, take a look at insertion sort : http://en.wikipedia.org/wiki/Insertion_sort

Output:

1,
2,
1,2,
3,
1,3,
2,3,
1,2,3,
4,
1,4,
2,4,
1,2,4,
3,4,
1,3,4,
2,3,4,
1,2,3,4,

Sorting
1,
2,
3,
4,
1,2,
1,3,
1,4,
2,3,
2,4,
3,4,
1,2,3,
1,2,4,
1,3,4,
2,3,4,
1,2,3,4,

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int comp (const void * elem1, const void * elem2) {
    unsigned int *f = (unsigned int*)elem1;
    unsigned int *s = (unsigned int*)elem2;
    unsigned int i;


    //printf("%d,%d,%d,%d,%d\n", f[0],f[1],f[2],f[3],f[4]);
    //printf("%d,%d,%d,%d,%d\n", s[0],s[1],s[2],s[3],s[4]);
    printf("\n");

    // Size comparison     
    if( f[4] > s[4] ) return 1;
    if( f[4] < s[4] ) return -1;

    // Value comparison
    for ( i = 0; i < 4; i++)
    {
        if (f[i] > s[i]) return  1;
        if (f[i] < s[i]) return -1;
    }

    return 0;
}

int main(int argc, char *argv[])
{
    unsigned int i, j, bits, i_max = (1U << 4);
    unsigned int *array;
    unsigned int index;

    array = calloc( 5*i_max, sizeof(unsigned int));

    // Non-sorted array
    for (i = 0; i < i_max ; ++i) {

        // Zero init for array
        memset(array + i*5, 0, 5*sizeof(*array));
        index = 0;

        for (bits = i, j = 0; bits; bits >>= 1, ++j) {

        if (bits & 1)
            {
                // Storage
                array[i*5 + index]   = j+1;

                index = (index + 1) % 4; // avoid buffer overflows
                array[i*5 + 4]   = array[i*5 + 4] + 1 ; // increment subset length

                //printf("%d,", array[i*5 + index - 1]);
            }
        }
        printf("\n");
    }

    // Print original array, without the zeros
    for (i =0; i < i_max; i++)
    {
        for(j = 0; j < 4 ; j++)
        {
            if( array[i*5 + j] )
                printf("%d,", array[i*5 + j]);
        }
        printf("\n");
    }


    printf ("Sorting\n");

    qsort (array, i_max, 5*sizeof(unsigned int), comp);


    // Print the sorted array, without the zeros
    for (i =0; i < i_max; i++)
    {
        for(j = 0; j < 4 ; j++)
        {
            if( array[i*5 + j] )
                printf("%d,", array[i*5 + j]);
        }
        printf("\n");
    }
    free(array);

    return 0;
}

Progeny

Admirable, but you are missing the empty set {}... so technically this does not generate the powerset – Skyward

Answer 5

I used this answer to make following code:

Basically you need to print nCr sequences for all r

#include <iostream>
#include <vector>

using namespace std;

 //This generates all nCr sequences
void display(const std::vector<int> & v, 
             std::vector<int>& comb, 
             int offset, int k) {
    if (k == 0) {
        std::cout<<"{";
        for(auto &x:comb)
            std::cout<<x<<",";
         std::cout<<"\b}"<<std::endl;
    return;
    }
    for (int i = offset; i <= v.size() - k; ++i) {
        comb.push_back(v[i]);
        display(v,comb,i+1, k-1);
        comb.pop_back();
    }
}

int main() {
    int n = 4;

     std::vector<int> v,comb;
    for (int i = 0; i < n; ++i) 
     v.push_back(i+1); 

    for (int i = 1; i <= n; ++i) 
        display(v,comb,0, i);

    return 0;
}

See here

Natashianatassia