Exactly. And so how to generate all bit patterns with only k 1's?
This is the heart of the problem, which has not yet been solved. It
would be very wasteful with n=10,000, k=2 to try all 2^10000 bit
patterns looking for the small number with only 2 bits set: 10000
choose 2, which is only abut 2^26, a _much_ smaller number.
A more efficient way is a simple recursion:
Let S = {a_1, a_2 .. a_n }
void select(Set S, int k, Set T)
{
if (k == 0) print T
else for i = 1 to n - k {
select( { a_(i+1) .. a_n }, k - 1, T union { a_i } )
}
}
If you're careful, you can implement the sets with arrays, in C. For
sets of integers:
void select(int *S, int nS, int k, int *T, int nT)
{
int i;
if (k == 0) print(T, nT);
else for (i = 0; i < nS - k; i++) {
T[nT] = S[i];
select(S + i + 1, nS - i - 1, k - 1, T, nT + 1);
}
}
Initiate with:
select(S, |S|, k, T, 0);
On Aug 24, 1:41 am, Chonku <[email protected]> wrote:
> Though the approach is correct, but I think it should say that Generate all
> bit strings of size n with k bits set. Where n is the
> number of elements in the set and k is the number of 1's in the string.
>
>
>
> On Sun, Aug 22, 2010 at 2:08 PM, R.ARAVINDH <[email protected]> wrote:
> > @raj
>
> > really cool
>
> > On Aug 22, 1:08 pm, Raj N <[email protected]> wrote:
> > > Generate all binary strings of length k. For eg: S={1,2,3,4,5} generate
> > all
> > > binary strings of length 5. 0 represents that particular number is absent
> > > and 1 for the presence of the number.
>
> > > On Fri, Aug 13, 2010 at 11:35 PM, asdf <[email protected]> wrote:
> > > > Most efficient algorithm to find all subsets of size K??
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to [email protected].
> > > > To unsubscribe from this group, send email to
> > > > [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> > <algogeeks%2bunsubscr...@googlegroups .com>
> > > > .
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
