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) =Union of [ Powerset(S – y) U { {y} U Q | Q is in Powerset(S – y) } ] over all y is in 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.

Note that the invariant after the first recursive call within the ith level of recursion
is that the 2^(n-(i+1)) subset(s) without the ith element y are
printed; the invariant after the second call is 2^(n-i) subset(s) are printed. Here i ranges from 1 through 
n. Each of these subsets has exactly the same combination of the first i-1 elements, which is again
one of the 2^(i-1) possible combinations. Whether we choose or leave y (the ith element),
gives two possibilities, making a total of 2 * 2^(i-1) possible fixed patterns of first i elements
printed for each of the 2^(n-i) combinations of the rest of the elements.

Extension of  Assignment 6.a (Home assignment)

Write a program that prints all permutations of n integers 1 through n,
in lexicographically increasing order as explained in class.

e.g.,

n=3,

123, 132, 213, 231, 312, 321

n=4,

1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341,
2413, 2431, 3124, and so on till 4321.

Print the n elements when
all the n elements are decided in the permutation sequence. A few
checks need to be done when we
proceed to generate the next lexicographic permutation;

it helps to see what we generated last and manipulate it to construct the
next lexicographic permutation.
We may observe how decreasing sequences detemine what we do next.

---

Course home