Re: Subsets from a set
- From: torbenm@xxxxxxxxxxxxx (Torben Ægidius Mogensen)
- Date: 14 Aug 2006 14:31:20 +0200
"stdazi@xxxxxxxxx" <stdazi@xxxxxxxxx> writes:
stdazi@xxxxxxxxx wrote:
Hello,
I was just playing with some coding problem, when I figured out I'll
need to retrieve all the subsets from a given set. As I'm not very good
at solving that kind of algorithms, the code produced would get too
dirty and slow, that's why I'm wondering if someone can provide me a
simple algorithm procedure or code snippet. The code I'm playing with
is made in C and uses arrays to emulate sets.
This is the best i could code :
#include <stdio.h>
#include <math.h>
static void subsets(int *s,size_t nel) {
unsigned i,v,c;
for (i=0;i<pow(2,nel);i++) {
putchar('{');
for (v=i,c=0;v;v>>=1,c++)
if (v&1)
printf(" %d " ,s[c]);
printf("}\n");
}
}
int main() {
int ourset[5]={1,2,3,4,5};
subsets(ourset,5);
return 0;
}
It's quite fast, the only thing that can be improved is the byte
checking loop which (now) checks every bit.
It breaks when the number of elements in the set are greater than 32
(or 64 if you use 64-bit integers).
Torben
.
- References:
- Subsets from a set
- From: stdazi@xxxxxxxxx
- Re: Subsets from a set
- From: stdazi@xxxxxxxxx
- Subsets from a set
- Prev by Date: Re: Interesting problem: automatic item categorization
- Next by Date: Re: Subsets from a set
- Previous by thread: Re: Subsets from a set
- Next by thread: Adding practical (runtime) facts to a program
- Index(es):
Relevant Pages
|
