Power set: Difference between revisions
Content added Content deleted
m (Link to local set, not Wikipedia.) |
(→{{header|C}}: removed second method: does the same thing, except in a convoluted and inefficient way) |
||
Line 164: | Line 164: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<lang c> |
<lang c>#include <limits.h> |
||
#include <limits.h> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 171: | Line 170: | ||
static void powerset(int argc, char** argv) |
static void powerset(int argc, char** argv) |
||
{ |
{ |
||
unsigned int i, j, bits, i_max = 1U << argc; |
|||
size_t j = 0; |
|||
if (argc >= sizeof(i) * CHAR_BIT) { |
|||
size_t bits = 0; |
|||
fprintf(stderr, "Error: set too large\n"); |
|||
size_t i_max = 1 << argc; |
|||
exit(1); |
|||
if (argc > sizeof(size_t) * CHAR_BIT) { |
|||
fprintf(stderr, "Error: set too large\n"); |
|||
exit(1); |
|||
} |
} |
||
for (i = 0 |
for (i = 0; i < i_max ; ++i) { |
||
printf("{"); |
|||
for (bits = i, j = 0; bits; bits >>= 1, ++j) { |
|||
printf("("); |
|||
if (bits & 1) |
|||
printf(bits > 1 ? "%s, " : "%s", argv[j]); |
|||
} |
|||
printf(first ? "%s" : " %s", argv[j]); |
|||
printf("}\n"); |
|||
} |
|||
} |
|||
printf(")\n"); |
|||
} |
|||
} |
} |
||
Line 198: | Line 191: | ||
powerset(argc - 1, argv + 1); |
powerset(argc - 1, argv + 1); |
||
return 0; |
return 0; |
||
}</lang>output<lang>% ./a.out 1 2 3 4 |
|||
} |
|||
{} |
|||
</lang> |
|||
{1} |
|||
{2} |
|||
Output: |
|||
{1, 2} |
|||
{3} |
|||
<pre> |
|||
{1, 3} |
|||
$ ./powerset 1 2 3 4 |
|||
{2, 3} |
|||
() |
|||
{1, 2, 3} |
|||
(1) |
|||
{4} |
|||
(2) |
|||
{1, 4} |
|||
{2, 4} |
|||
(3) |
|||
{1, 2, 4} |
|||
{3, 4} |
|||
(2 3) |
|||
{1, 3, 4} |
|||
{2, 3, 4} |
|||
(4) |
|||
{1, 2, 3, 4}</lang> |
|||
(1 4) |
|||
(2 4) |
|||
(1 2 4) |
|||
(3 4) |
|||
(1 3 4) |
|||
(2 3 4) |
|||
(1 2 3 4) |
|||
</pre> |
|||
Alternate implementation: |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
typedef const char *SetType; |
|||
typedef int bool; |
|||
typedef struct setStruct { |
|||
int count; |
|||
SetType *elements; |
|||
void (*printer)(SetType ); |
|||
bool nlAfterElements; |
|||
} *Set; |
|||
/* Could probly use same struct as above for this */ |
|||
typedef struct powerSetStruct { |
|||
int count; |
|||
Set *elements; |
|||
void (*printer)(Set); |
|||
bool nlAfterElements; |
|||
} *PowerSet; |
|||
void PrintSet( Set s); |
|||
PowerSet GetPowerSet( Set set) |
|||
{ |
|||
int ix, n, j; |
|||
int max = 1<<set->count; // Assuming count < 32 |
|||
PowerSet ps = malloc( sizeof(struct powerSetStruct)); |
|||
if (ps) { |
|||
ps->elements = malloc( max*sizeof(Set)); |
|||
ps->count = max; |
|||
ps->printer = PrintSet; |
|||
ps->nlAfterElements = 1; |
|||
for (ix=0; ix<max; ix++) { |
|||
int setsize = 0; |
|||
Set se = malloc(sizeof(struct setStruct)); |
|||
for (j=0; j<set->count; j++) |
|||
if (ix & (1<<j)) setsize++; |
|||
if (setsize > 0) { |
|||
se->elements = malloc(setsize *sizeof(SetType)); |
|||
n = 0; |
|||
for (j=0; j<set->count; j++) { |
|||
if (ix & (1<<j)) { |
|||
se->elements[n] = set->elements[j]; |
|||
n++; |
|||
} |
|||
} |
|||
} |
|||
else { |
|||
printf("No elements in set %d\n", ix); |
|||
se->elements = NULL; |
|||
} |
|||
se->count = setsize; |
|||
se->printer = set->printer; |
|||
se->nlAfterElements = set->nlAfterElements; |
|||
ps->elements[ix] = se; |
|||
} |
|||
} |
|||
return ps; |
|||
} |
|||
void PrintSet( Set s) |
|||
{ |
|||
const char *sep = ""; |
|||
int ix; |
|||
printf("{"); |
|||
for (ix=0; ix<s->count; ix++) { |
|||
printf("%s ", sep); |
|||
s->printer(s->elements[ix]); |
|||
sep = (s->nlAfterElements)? ",\n " :","; |
|||
} |
|||
printf(" }"); |
|||
} |
|||
void PrintString( const char *str) |
|||
{ |
|||
printf("%s", str); |
|||
} |
|||
int main() |
|||
{ |
|||
const char *eles[] = {"Red","Grn","Blu","Ylo"}; |
|||
struct setStruct aSet = { 4, eles, PrintString, 0 }; |
|||
PowerSet p = GetPowerSet( &aSet); |
|||
PrintSet(&aSet); printf("\n"); |
|||
PrintSet( (Set)p ); printf("\n"); |
|||
return 0; |
|||
}</lang> |
|||
Output: |
|||
<pre>{ Red, Grn, Blu, Ylo } |
|||
{ { }, |
|||
{ Red }, |
|||
{ Grn }, |
|||
{ Red, Grn }, |
|||
{ Blu }, |
|||
{ Red, Blu }, |
|||
{ Grn, Blu }, |
|||
{ Red, Grn, Blu }, |
|||
{ Ylo }, |
|||
{ Red, Ylo }, |
|||
{ Grn, Ylo }, |
|||
{ Red, Grn, Ylo }, |
|||
{ Blu, Ylo }, |
|||
{ Red, Blu, Ylo }, |
|||
{ Grn, Blu, Ylo }, |
|||
{ Red, Grn, Blu, Ylo }}</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |