Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Generate All Subsets Of A Set

DZone's Guide to

Generate All Subsets Of A Set

·
Free Resource
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 
  
   

/* 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;
}

  
Topics:

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}