C Program

profileadusar75

Write a C program that uses recursion to print out all ????-element subsets of the ????-element set {1,2,3,…,????}, where both ???? and ???? are given on the command line. Recall that the Binomial Coefficient ????(????,????) is defined to be the number of such subsets, and that these numbers can be computed recursively using Pascal's identity. For instance, if ????=4 and ????=2, one verifies ????(4,2)=6, and that the 2-element subsets of {1,2,3,4} are: {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}. The core idea of our recursive solution is the same as in the proof  of Pascal's identity.

????(????,????)={ 1 if ????=0 or ????=???? ????(????−1,????−1)+????(????−1,????) if 0<????<????

At each level of the recursion, we consider a particular element ???? in the set {1,2,3,…,????}. First construct all ????-elements subsets that include ????, and then construct those subsets that exclude ????. The following box trace illustrates the case ????=3, ????=2.

print {1,2} print nothing

since ????>1

print {1,3} print nothing print {2,3} print nothing

since ????>0 since ????>0

Observe that the element ???? under consideration at each level is in bold. Green highlight indicates that an element has been included in the subset, and red highlight indicates exclusion. For instance, at the top level, the element 1 is being considered. The left branch includes 1, and the right branch excludes it. The variable ???? always indicates the number of elements yet to be selected, so at each left branch ???? is decremented, while at each right branch it stays the same. When we reach a box in which ????=0, no more elements need to be selected, so we print the chosen (green) elements. These form a completed subset of the required size. At each box, the number of candidates remaining (i.e. those not highlighted) is ????−????+1. If we reach a box in which ???? is greater than this number, i.e. ????>????−????+1, we return without printing anything, since that box cannot generate a subset of size ????.

As an exercise, construct a box trace for the case ????=4, ????=2, obtaining the six 2-element subsets listed above. (Be sure to use a large piece of paper when you do this.) It is highly recommended that you complete

{

1 , 2, 3}, ????=2, ????=1

1 , 2 , 3}, ????=1, ????=2 1 , 2 , 3}, ????=2, ????=2

1 , 2 , 3 }, ????=0, ????=3 1 , 2 , 3 }, ????=1, ????=3

1 , 2 , 3 }, ????=1, ????=4

1 , 2 , 3 }, ????=1, ????=3

1 , 2 , 3 }, ????=1, ????=4 1 , 2 , 3 }, ????=0, ????=4 1 , 2 , 3 }, ????=0, ????=4

1 , 2 , 3 }, ????=2, ????=3

2

several such box traces by hand before you attempt to write any code for this project. In general, you cannot

instruct a computer to do something that you cannot do yourself.

Representation of Subsets

We will use the following well-known approach to represent a subset of {1, 2, 3 … , ????}. First, create and

array ????[ ] of length ???? + 1 (or more), then fill it with 0's and 1's according to the following rule. For any ????

in the range 1 ≤ ???? ≤ ????, set

????[????] = {

1 iff ???? is included in the subset

0 iff ???? is excluded from the subset

Observe that the array element ????[0] is not be used, and if the length of ????[ ] is greater than ???? + 1, then the

elements to the right of ????[????] are also not used. Thus the bit-array ????[1 ⋯ 7] = (0, 0, 1, 0, 1, 1, 0) represents

the subset {3, 5, 6} of {1, 2, 3, 4, 5, 6, 7}. As an exercise, re-do the above box trace (and any other box traces

you have performed) representing each subset as a bit array. (Note this exercise is essential to success in

this assignment, don't fail to do it.)

Some students may dislike the idea of wasting ????[0]. It is possible to write the required functions for this

assignment without using this convention, but then those functions would not be compatible with the tests

used to evaluate your program. To get full credit, you must represent subsets of {1, 2, 3, … , ????} with an int

array of length (at least) ???? + 1 containing only 0's and 1's in ????[1], ????[2], ????[3], … , ????[????]. You can put

something in ????[0] if you like, or something in ????[(???? + 1) ⋯ ⋯ ], but those values will not be examined

during grading of your project.

There are two required functions in this assignment. A function with the heading

void printSet(int B[], int n))

will be included that prints the subset of {1, 2, 3, … , ????} represented by the bit-array ????[1 ⋯ ????] using braces

("{" and "}"), commas and positive integers. Thus if ????[ 1 ⋯ 7] is in the state (∗ ,0, 0, 1, 0, 1, 1, 0), then the

string "{3, 5, 6}" will be printed. Here ∗ represents whatever is in ????[0]. Note that the empty set will

be represented as an array of all 0's, and the above function will print the string "{ }". (That’s a pair of

open and closing braces with a single space between.) Your program will include another function with

heading

void printSubsets(int B[], int n, int k, int i)

that implements the recursive algorithm described above. Specifically, a call to printSubsets(????, ????, ????, ????)

will print solutions to the following subinstance: assume that the elements {1, 2, … , (???? − 1)} have already

been decided upon (included or excluded), then extend that partial solution in all possible ways to obtain a

????-element subset of {1, 2, 3, … , ????}.

You may assume that in all tests of your program, the value ???? will not exceed 100. Therefore you should

#define a constant macro MAX_SIZE to be 100, and define the array ????[ ] to be of length MAX_SIZE+1.

(This is why there may be unused array elements to the right of ????[????].) Function main() will read

command line arguments, define and initialize the int array ????[ ], then call the required functions as

appropriate. You may of course include other helper functions as you see fit.

3

Program Operation

Your program will be called Subset.c and will operate as follows.

$ Subset

Usage: Subset n k (n and k are ints satisfying 0<=k<=n<=100)

$ Subset foo bar

Usage: Subset n k (n and k are ints satisfying 0<=k<=n<=100)

$ Subset 1.2 3.4

Usage: Subset n k (n and k are ints satisfying 0<=k<=n<=100)

$ Subset 2 4

Usage: Subset n k (n and k are ints satisfying 0<=k<=n<=100)

$ Subset 4 2

{1, 2}

{1, 3}

{1, 4}

{2, 3}

{2, 4}

{3, 4}

$ Subset 5 3

{1, 2, 3}

{1, 2, 4}

{1, 2, 5}

{1, 3, 4}

{1, 3, 5}

{1, 4, 5}

{2, 3, 4}

{2, 3, 5}

{2, 4, 5}

{3, 4, 5}

$ Subset 3 3

{1, 2, 3}

$ Subset 3 0

{ }

$ Subset 8 0

{ }

$

As you can see, if anything other than two command line arguments are supplied, or if those two arguments

cannot be parsed as ints, or if they can be parsed as ints, but do not satisfy the inequality 0 ≤ ???? ≤ ???? ≤

MAX_SIZE, then a usage message will be printed, and the program will terminate. The required subsets are

printed one to a line. Your program must match the above format (including the usage message) exactly to

receive full credit.

What to turn in

Submit the files README, Makefile, and Subset.c to the assignment pa1 before the due date. Your

Makefile must create an executable jar file called Subset, and must include a clean utility that removes

all .class files as well as the jar file Subset itself. 

    • 4 years ago
    • 16
    Answer(0)