Name: Anonymous 2010-10-12 22:27
c++ find the power set of a set containing 40 integers in polynomial time
// anus.cpp
// @author [YOUR NAME HERE]
// Reads a set of forty numbers from command line arguments
// and prints each element of the power set
#include <cstdlib>
#include <cstdio>
#include <vector>
#include "anus.h" // Left as an exercise to the reader
static int FORTY = 40;
vector<int>* build_subset(vector<int> &set, vector<bool> &bits) {
vector<int> *result = new vector<int>;
for(int i=0; i < bits.size(); i++) {
if (bits[i]) {
result->push_back(set[i]);
}
}
return result;
}
void print_subset(vector<int>* subset) {
printf("[");
for(int i=0; i < subset->size(); i++) {
int n = subset->at(i);
printf("%d ", n);
}
printf("]\n");
}
using std::cout;
using std::endl;
int main(int argc, char* *argv) {
if (argc < FORTY+1){
printf("Usage: anus [first number] [second number] .. [40th number]\n");
return 1;
}
vector<int> set;
for (int i=1; i < FORTY+1; i++) {
set.push_back(atoi(argv[i]));
}
// empty set
vector<bool> empty(FORTY, false);
print_subset(build_subset(set, empty));
long propersubsets = 1099511627776L; // 2 ^ 40
for (long i=0; i < propersubsets; i++) {
vector<bool> bits;
for (long j=0; j < FORTY; j++) {
bool on = ((i & j) == j);
bits.push_back(on);
}
print_subset(build_subset(set, bits));
}
}