Today we’ll have a look at how to print all the sub-groups of a given group

How exciting is that?!

As an example, let’s look at the following group: G = \{1,2,3,4\} should produce all the subgroups:

{Empty}
{1}, {2}, {3}, {4}
{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}
{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}
{1,2,3,4}


As you can see, there are 2^n different subgroups of all the possible sizes, where n= |G| (in our example above, |G| = n = 4)

Using “binary words”

A binary word is nothing but a number in binary!!

The importance of the binary representation is that we can use it to mask off the numbers which we’re not interested to include in our output.

For example: the subgroup \{3\} is represented by the binary word 0010 because our group G=\{1,2,3,4\} and 1,2,4 are not included in the subgroup.
A visual explanation:

Group:  1 , 2, 3, 4
Binary: 0   0  1  0
        |   |  |  |
        V   V  V  V
SubGrp: -   -  3  -   => {3}

*NOTE* the symbol | is to represent an arrow pointing downwards!
                  V

So basically, we’re iterating over all the binary words ranging from 000... to 1111...

To better understand this analogy, let’s consider the group {A,B,C}:

Binary |  sub group
-------+------------
 0 0 0 |  {Empty}
-------+------------
 0 0 1 |  {C}
-------+------------
 0 1 0 |  {B}
-------+------------
 0 1 1 |  {B, C}
-------+------------  
 1 0 0 |  {A}
-------+------------   
 1 0 1 |  {A , C}
-------+------------   
 1 1 0 |  {A, B}
-------+------------   
 1 1 1 |  {A, B, C}

For each binary word, we gotta investigate at which places there are 1’s in order to print them. Thus we need O(log(n)) time to check each binary word.

Let’s dive into the Code!

#include <stdio.h>
#include<stdlib.h>
#include <math.h>
void subGroups2(int* group, int n) {
	if (!group) {
		printf("{empty}\n");
		return;
	}
	double mask = pow(2,n);
	printf("Empty\n");
	int pivot = 1, c = 0;
	for (int i = 1; i < mask; i++) {
		while (pivot <= mask) {
			if ((i & pivot) == pivot) {
				printf("%d, ", group[c]);
			}
			pivot = pivot << 1;
			c++;
		}
		pivot = 1;
		c = 0;
		printf("\n");
	}
}
/***************************************/
int main() {
   int G[] = { 1, 2, 3, 4, 5 };
   subGroups2(G, 5);
   return 0;
}

Output:

Empty
1, 
2, 
1, 2, 
3, 
1, 3, 
2, 3, 
1, 2, 3, 
4, 
1, 4, 
2, 4, 
1, 2, 4, 
3, 4, 
1, 3, 4, 
2, 3, 4, 
1, 2, 3, 4, 
5, 
1, 5, 
2, 5, 
1, 2, 5, 
3, 5, 
1, 3, 5, 
2, 3, 5, 
1, 2, 3, 5, 
4, 5, 
1, 4, 5, 
2, 4, 5, 
1, 2, 4, 5, 
3, 4, 5, 
1, 3, 4, 5, 
2, 3, 4, 5, 
1, 2, 3, 4, 5,

If you count them carefully, you’ll see that there are 32 sub-groups of all the sizes from 0(Empty) to 5.

This implementation takes O(2^n)
Where  2^n are the number of binary words. For each binary word, we do O(n) “peeks” to count the 1’s and 0’s!

Level Two!!

You  can also take it a step further and print only the sub-groups of a certain size..
Since the concept remains the same, I’ll attach only the code:

/*
 * Prints the sub-groups of G with the cerrtain sizes 'subSize
 */
void subGroups3(int* group, int n, int subSize) {
	if ((!group) || (subSize < 0) || (subSize > n)) {
		return;
	}

	int mask = 1;
	for (int i = 0; i < n; i++) {
		mask *= 2;
	}

	int pivot = 1, c = 0;
	for (int i = 1; i < mask; i++) {
		while (pivot <= mask) {
			if ((i & pivot) == pivot) {
				c++;
			}
			pivot = pivot << 1;
		}

		pivot = 1;
		if (c != subSize) {
			c = 0;
			continue;
		}
		c = 0;
		while (pivot <= mask) {
			if ((i & pivot) == pivot) {
				printf("%d, ", group[c]);
			}
			c++;
			pivot = pivot << 1;
		}

		pivot = 1;
		c = 0;
		printf("\n");
	}
}
/**********************************/
int main() {
	int G[] = { 1, 2, 3, 4, 5 };
	subGroups3(G, 5, 2);
	return 0;
}

Output:

1, 2, 
1, 3, 
2, 3, 
1, 4, 
2, 4, 
3, 4, 
1, 5, 
2, 5, 
3, 5, 
4, 5,
Advertisements