Power set: Difference between revisions

Content added Content deleted

Inline

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