Program assignment about recursion

1

CMPS 12B

Introduction to Data Structures

Programming Assignment 1

In this assignment you will write a 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 essentially the same as in the proof of Pascal's identity. (See notes from 4-2-19 to see that proof.)

𝐶(𝑛, 𝑘) = { 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, … , 𝑛}. We 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. Also 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 remaining candidates 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

several such 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.

{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

Representation of Subsets

We will use the following well-known approach to represent subsets of {1, 2, 3 … , 𝑛}. First initialize an int array 𝐵[ ] of length 𝑛 + 1, and fill it with 0's and 1's. For any 𝑖 in the range 1 ≤ 𝑖 ≤ 𝑛, set

𝐵[𝑖] = { 1 iff 𝑖 is included 0 iff 𝑖 is excluded

The array element 𝐵[0] will not be 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 throwing away 𝐵[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 𝑛 + 1 containing only 0's and 1's in 𝐵[1], 𝐵[2], 𝐵[3], … , 𝐵[𝑛]. You can put something in 𝐵[0] if you like, but it will not be examined during grading of your project.

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

static String setToString(int[] B)

will be included that converts a bit-array to the corresponding String representation of a set using braces

("{" and "}"), commas and positive integers. Thus if 𝐵[ ] is in the state (∗ ,0, 0, 1, 0, 1, 1, 0), then the string "{3, 5, 6}" will be returned. Here ∗ represents whatever you choose to put in 𝐵[0]. Note that the empty set will be represented as an array of all 0's, and the above function will return the string "{ }". (That’s a

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

with heading

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

That implements the recursive algorithm we have been discussing. Function main() will read command

line arguments, initialize an int array of appropriate size, then call the required functions as appropriate.

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

Program Operation

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

% Subset 4 2

{1, 2}

{1, 3}

{1, 4}

{2, 3}

{2, 4}

{3, 4}

% Subset foo bar

Usage: Java Subset <int> <int>

% Subset 2 4

Usage: Java Subset <int> <int>

% Subset 6

Usage: Java Subset <int> <int>

3

% Subset 8 0

{}

% 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

{}

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 ≤ 𝑘 ≤ 𝑛, 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.java 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. See Lab Assignment 1 to learn how to do this. Please

start early and ask plenty of questions in lab sessions and office hours.