CS13002 Programming and Data Structures

Section: 5/E, Spring 2006

Assignment 5

This assignment is an extension of Assignment 4. You have counted the numbers of nonbelligerent collections on a line and on a circle for a group of n persons. Now your task is to find out and print all the nonbelligerent collections.

I propose a similar recursive function. Instead of sending the last person chosen so far, you would send in an array all the persons chosen so far. Print that collection. Then decide what are the minimum and maximum bounds (call them m and M respectively) on the next choice. For each i between m and M, choose the next person to be the i-th one. Save i in the array and call the function recursively.

Write two separate recursive functions, one for nonbelligerent collections on a line, the other for nonbelligerent collections on a circle.

Report the output of your program for n=8,10,12.

As an added challenge, you may think about printing the groups neatly. One possibility is to print each group in a single line. This results in a long list of groups. Another possibility is to print all the groups in a single line. That leads to a very wide line. A better strategy is to print groups in a line as long as the length of the line does not exceed 80. If printing the next group lets the width of the current line exceed this capacity, insert a line break. I leave it to you how you decide good points for line breaks. My solution is shown in the sample output below.

Sample output

How many people? 5
********************************************************************************
Nonbelligerent collections on a line:
{} {1} {1,3} {1,3,5} {1,4} {1,5} {2} {2,4} {2,5} {3} {3,5} {4} {5}
Total count = 13
********************************************************************************
Nonbelligerent collections on a circle:
{} {1} {1,3} {1,4} {2} {2,4} {2,5} {3} {3,5} {4} {5}
Total count = 11
********************************************************************************

How many people? 7
********************************************************************************
Nonbelligerent collections on a line:
{} {1} {1,3} {1,3,5} {1,3,5,7} {1,3,6} {1,3,7} {1,4} {1,4,6} {1,4,7} {1,5}
{1,5,7} {1,6} {1,7} {2} {2,4} {2,4,6} {2,4,7} {2,5} {2,5,7} {2,6} {2,7} {3}
{3,5} {3,5,7} {3,6} {3,7} {4} {4,6} {4,7} {5} {5,7} {6} {7}
Total count = 34
********************************************************************************
Nonbelligerent collections on a circle:
{} {1} {1,3} {1,3,5} {1,3,6} {1,4} {1,4,6} {1,5} {1,6} {2} {2,4} {2,4,6}
{2,4,7} {2,5} {2,5,7} {2,6} {2,7} {3} {3,5} {3,5,7} {3,6} {3,7} {4} {4,6}
{4,7} {5} {5,7} {6} {7}
Total count = 29
********************************************************************************


[Submission site] [Lab home] [Course home]