Search code examples
c++powerset

Problems with writing powerset code


I'm trying to generate the powerset of a set and I wrote this code. The problem is, when user enter two similar member of the set it dosen't work properly. What can I do? Here is my code:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

char obtain(char *p,int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        cout<<"enter member"<<(i+1)<<"\n";
        cin>>*(p+i);
    }
    return *p;
}

void set_display(char *p,int n)
{
    cout<<"{";
    for(int i=0;i<n;i++)
    {
        cout<<*(p+i)<<",";
    }
    cout<<"}";
}

void powset(char *p,int n)
{
    unsigned int m = (double)pow((double)2, n);
    int i, j;
    for(i = 0; i < m; i++)
    {
        cout<<"{";
        for(j = 0; j < n; j++)
        {
            if(i& (1<<j))
                cout<<*(p+j);
        }
        cout<<"}\n";
    }
}

Solution

  • Ok I could not debug your code where you are missing. but since you posted your question I written an code in pure C. May be you find it helpful.

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    int main(int argc, char* argv[]){
        int N;
        char y[20]={0};
        int i,j;
        y[0] = 'a';
        y[1] = 'b';
        y[2] = 'c'; 
        N = 3;
        int powerSet;
        powerSet=pow(2,N);
        for(i = 0; i<(powerSet);i++){
            for(j=0;j<N;j++){
                if((i & (1<<j))){
                    printf("%c ",y[j]);
                }
            }
            printf("\n");
        }           
        printf("\n");
        return EXIT_SUCCESS;
    }
    

    And its working:

    :~$ gcc x.c -lm -Wall
    :~$ ./a.out 
    
    a 
    b 
    a b 
    c 
    a c 
    b c 
    a b c 
    

    [ANSWER]

    You error case: When two symbols are same.

    y[0] = 'a';
    y[1] = 'a';
    y[2] = 'c'; 
    
    :~$ ./a.out 
    
    a 
    a 
    a a 
    c 
    a c 
    a c 
    a a c 
    

    But this is wrong according to set theory. Because in Set we can't have same element twice (more then onec). BUT ALSO INPUT IS WRONG: (a, a, c) is not a set. So code is usable.