Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

« Newer Snippets
Older Snippets »
Showing 1-2 of 2 total  RSS 

Generate all subsets of a set

This code generates all the subsets of {1, 2, ..., n} and prints them.

This also contains a very fast binary counter implementation.

See this for further explanations.

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
	int i;
	printf("{ ");
	for (i = 0; i < n; ++i)
		if (mask[i])
			printf("%d ", i + 1); /*i+1 is part of the subset*/
	printf("\b }\n");
}

/* Generates the next mask*/
int next(int mask[], int n) {
	int i;
	for (i = 0; (i < n) && mask[i]; ++i)
		mask[i] = 0;

	if (i < n) {
		mask[i] = 1;
		return 1;
	}
	return 0;
}

int main(int argc, char *argv[]) {
	int n = 3;

	int mask[16]; /* Guess what this is */
	int i;
	for (i = 0; i < n; ++i)
		mask[i] = 0;

	/* Print the first set */
	printv(mask, n);

	/* Print all the others */
	while (next(mask, n))
		printv(mask, n);

	return 0;
}

subset? and superset? functions

    subset?: func [
        {Returns true if A is a subset of B; false otherwise.}
        a [series! bitset!]
        b [series! bitset!]
    ] [
        empty? exclude a b
    ]

    superset?: func [
        {Returns true if set1 is a superset of set2; false otherwise.}
        set1 [series! bitset!]
        set2 [series! bitset!]
    ][
        subset? set2 set1
    ]
« Newer Snippets
Older Snippets »
Showing 1-2 of 2 total  RSS