call it as : bipartition(a,-1,2) . coz at the very first time k is being
incremented so it needs intiiale value -1.
On Sat, Sep 3, 2011 at 8:46 PM, Siddhartha Banerjee thefourrup...@gmail.com
wrote:
please check out the code, doesnt give right solution on running...
or perhaps i missed
Here is my soluion .
void bipartition(int a[],int p,int max)
{
if(p==max){return ;}
p++;
for(int i=p;imax;i++)
{
if(result[i]==1) continue;
result[i]=1;
print_bipartition(result,a,max);
bipartition(a,i,max);
result[i]=0;
}
}
void print_bipartition(int result[],int
this line is unnecessary
if(result[i]==1) continue;
I think this algo is good enough. But any improvements?
--
*MOHIT VERMA*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
please check out the code, doesnt give right solution on running...
or perhaps i missed something... how should you call your function? if array
is a={1,2,3} you call from main function as
bipartition(a,0,2), right???
--
You received this message because you are subscribed to the Google Groups
Piyush Has Correct Idea, If You Have N elements in Set/Array You Will Have
Maximum 2^n Subsets (Power Set), Now Problem Reduced to generate the all
such subsets , it will take O(2^n*n ) time , Now number of Valid
Bipartitions are exactly n/2 .
Note: Power Set includes 0 as well
Correct me
@shasank:
how come the valid bipartition s are n/2..
those should be at least n right?
ex:
{1,2,3}
{1},{2,3}
--{1,2},{3}
--{},{1,2,3}
If this is correct , then for printing sake it takes O(n^2) .
correct me if I'm wrong.
On Fri, Sep 2, 2011 at 2:48 PM, WgpShashank
no of valid bipartitions are 2^n, thats what he meant I guess... ( if you do
not want null set as one of the partitions then subtract 1 from answer...)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to