nitish712
BAN USER@ashish In order to improve it, i guess we need to find a faster way of finding the positions of set bits...it is as follows:
For each number 'p' that we convert into binary .. do as follows:
int itr2=0;
while(p>0)
{
int tmp=p;
p = p&(p-1);
tmp-=p;
int pos = log2(tmp);
subset[itr2++]=str[pos];
}
subset[itr2]='\0';
The time complexity now will be:
total number of set bits from 0 to 2^n-1 = n*2^(n-1) = O(n*2^n).
But the advantage is that running time is reduced to nearly half of the previous algorithm.
I guess this can't still be reduced.. :) :)
#include <stdio.h>
#include <string.h>
int main()
{
//assuming the string has distinct characters... (or else one can also pick out the distinct chars ..)
char str[20];
strcpy(str, "abcdef");
int len = strlen(str);
int start_val=(1<<len)-1;
char subset[20];
int itr1, itr2;
while(start_val >=0)
{
int tmp=start_val;
itr1=itr2=0;
while(itr2!=len)
{
if(tmp&1)
subset[itr1++] = str[itr2];
tmp >>=1;
itr2++;
}
subset[itr1]='\0';
printf("%s\n", subset);
start_val--;
}
return 0;
}
This code will print all possible subsets of the given string.
- nitish712 June 03, 2013
@amnesiac.. the inner loop is for selecting which letters are to be kept in the current subset. This is decided by checking the set bits of the current number('tmp' in this case). :) :)
- nitish712 June 04, 2013