|
=={{header|C}}==
<lang c>#include <limits.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
static void powerset(int argc, char** argv)
{
size_tunsigned int i, j, bits, i_max = 01U << 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 ; i < i_max ; ++i) {
int first = 1printf("{");
for (bits = i, j = 0; bits; bits >>= 1, ++j) {
printf("(");
for (bits = i, j = 0 ;if (bits ; bits >>=& 1, ++j) {
if printf(bits &> 0x1)1 {? "%s, " : "%s", argv[j]);
}
printf(first ? "%s" : " %s", argv[j]);
first = 0printf("}\n");
}
}
printf(")\n");
}
}
powerset(argc - 1, argv + 1);
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, 2)4}
{2, 4}
(3)
({1, 3)2, 4}
{3, 4}
(2 3)
({1 2, 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++}}==
|