CS13002 Programming and Data Structures |
(Autumn semester) Section A |
Assignment Set - 6
Please write your Roll Number, Name and Assignment Number at the header of each program.
Assignment 6.a: Filename: a6a.c
If S is a set of n elements, the powerset of S is the set of all possible subsets of S.
For example, if S = {a, b, c}, then powerset(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }.
Write a recursive function to print the powerset of a set of characters (stored in an array). Assume that the size of S is less than or equal to 10.
Write a program that calls this function for S = {a, b, c, d} and S = {u, v, w, x, y, z}.
Hint: One recursive formulation of the problem is as follows:
Powerset(S) = Powerset(S – y) U { {y} U Q | Q Î Powerset(S – y) } where y Î S
Suppose we associate a flag with each variable indicating its membership in the subset. Therefore to print powerset(S), we recursively print powerset(S – y) with the flag of y set to absent and then again print powerset(S – y) with the flag of y set to present so that y is appended to all subsets of S – y.