This blog is under construction

Saturday 13 July 2013

C program to print subsets of the given set

Write a C program to print subsets of the given set.


  #include <stdio.h>
  #include <stdlib.h>
  #include <math.h>

  int main() {
        int i, j, count, num, *data;

        /* get the number of inputs from user */
        printf("Enter the number of elements:");
        scanf("%d", &num);

        /* allocate memory to store the elements */
        data = (int *)malloc(sizeof(int) * num);

        /* get the elements from the user */
        for (i = 0; i < num; i++) {
                printf("Data[%d]: ",i);
                scanf("%d", &data[i]);
        }

        /* 2^num - indicates the possible no of subsets */
        count = pow(2, num);

        /* print the empty set first */
        printf("Subsets:\n{ }\n");
        for (i = 1; i < count; i++) {
                printf("{");
                /*
                 * To form subsets, we need to consider binary values
                 * with "num" bits.  If num is 3, then the possible 
                 * number of subsets is 2^3 = 8.  And we need to consider
                 * binary values with 3 bits.(000, 001, 010, 011, 100,
                 * 101, 110, 111)ie. decimal values 0 to 7.  Then form
                 * the subsets using the above manipulated binary value.
                 * If any of the bit(in binary value) is set, then note
                 * the bit index.  Use the same index value to fetch the
                 * data from the input array.  Suppose, 001 is the value.
                 * Here, 0th bit is set.  So, the element at index 0
                 * from input array needs to cosidered for subset outputs.
                 */
                for (j = 0; j < num; j++) {
                        /* 
                         * checking jth bit is set in i.  If
                         * it is set, then fetch the element at
                         * jth index in data array
                         */
                        if (i & (1 << j)) {
                                printf("%d ", data[j]);
                        }
                }
                printf("}\n");
        }
        return 0;
  }


Note:
gcc subsets.c -lm => linked math library since we have used math function pow().

  Output:
  jp@jp-VirtualBox:~/$ ./a.out
  Enter the number of elements:3
  Data[0]: 1 
  Data[1]: 2
  Data[2]: 3
  Subsets:
  { }
  {1 }
  {2 }
  {1 2 }
  {3 }
  {1 3 }
  {2 3 }
  {1 2 3 }


No comments:

Post a Comment