CS146            Program Assignment 2.  IC-base for paths

Prof. Sin-Min Lee

Due date: Feb. 26,2004

IC-base of paths

 

We will explore some questions about ways (call partitions) in which a whole number can be broken up into a sum of whole numbers (for instance, 9 can be partitioned into 5 + 2 + 1 + 1). The partitions on a number n correspond to the set of solutions (j1,…,jn) to the Diophantine equation


For example, the partitions of four, given by (1, 1, 1, 1), (1, 1, 2), (2, 2), (4), and (1, 3) correspond to the solutions(j1,j2,j3,j4)=

(4,0,0,0) = 4 * 1,

(2, 1, 0, 0) = 2 * 1 + 1 * 2,

(0, 2, 0, 0) = 0 * 1 + 2 * 2,

(0, 0, 0, 1) = 0 * 1 + 0 * 2 + 0 * 3 + 1 * 4,

and

(1, 0, 1, 0).= 1 * 1 + 0 * 2 + 1 * 3

So, there are five different partitions of four.

 

Figure 1. showing the six different partitions of five

 

In 1740, German mathematician Naude wrote to Euler to ask in how many ways a given positive integer can be expressed as a sum of r distinct positive integers. This problem was quickly solved by Euler.

First Euler introduced the idea of a partition of a positive number n into r parts as a sequence, n1<n2<…<nr, of positive integers such that n= n1<n2<…<nr where the ni are the parts.  As an example, the partitions of 4 are:

1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, 4; as is shown above.


He then let p(n) denote the number of partitions of n into any number of parts, where p(0) = 1.

Ex: p(4) = 5 because there are five different partitions of four.

  In order to study the sequence {p(n)}, he introduced the concept of a generating function , and showed that
 

What you have to do is:

(1)   Given an integer n and an integer p which is smaller than n, we want to generate all partition into p parts of the form (1,2,a3,a4,…,ap)

Partitions of an Integer

A partition of an integer, n, is a set of positive integers, n1, ..., nm that add up to n. (The partitions of an integer n are related to the partitions of a set of size n.) The partitions of n can be enumerated by a simple recursive routine: 

 
function partition(n, limit, answer)
 { var i;
   if(n > 0)
     for(i = min(n, limit); i > 0; i --)
       partition(n-i, i, answer now including i);
   else
     process the answer
 }//partition
 
//initial call:
   partition(n, n, initial empty answer);
 

The exact form of the "answer" depends on what you want to do with a partition, but it represents it in some way, e.g. as an array of integers. The extra parameter, "limit", ensures that each partition is in non-increasing order, e.g. 3+1+1, 1+3+1 and 1+1+3 are all considered to be equivalent and the algorithm only creates the first of these.

 

(2)   Form all the possible p permutations for a special partition.

For example if you have array  [1,2,3,4] it will print 1234,2134,2314,2341,1324, 1342, and so on - 4! permutations.

You can use the following reference for algorithms which generate all permutations:

[1]Robert Sedgewick. Algorithms (Second Edition). Addison-Wesley Publishing Company, August 1989.

[2]Donald E. Knuth. The Art of Computer Programming (Volume 3 /Sorting and Searching). Addison-Wesley Publishing Company, 1973.

[3]Jacques Arsac. Foundations of Programming. Academic Press Inc. (London) LTD. 1985.

Or other sources from Internet.

(3)   For each permutation (represented as p)  (p(1), p(2),…., p(p-1), p(p))

 Create an array       A1[p(1), p(2),…., p(p-1), p(p)]

A2[p(1)+ p(2), p(2)+ p(3),…, p(p-2)+ p(p-1), p(p-1)+ p(p)]

A3[p(1)+ p(2)+ p(3), p(2)+ p(3)+ p(4),…, p(p-3)+ p(p-2)+ p(p-1), p(p-2)+ p(p-1)+ p(p)]

…

until

…

Ap[p(1)+ p(2)+ p(3)+…+p(p)].

 

Now create a new array by appending the elements of== A1,A2,…,Ap together, call this array B.

(4)   Use any sorting algorithm sort the numbers in array B .

(5)   If the sorted number of B is of the form : 1a,2b,3c,… we say the permutation is good, print this permutation.

 

Goal: Write an interactive program (in Java), which allows a user to enter integers for n and p. It will provide all the good partitions and good permutations.

 

Program Input: The program should allow a user to input the number n and p. Your program will create an array, permutations and sorting. It must also be user friendly!

 

Program Output: The sequence of good partitions and good permutations.

Suggestion: Use any existing software to generate permutations and sorting. The following link has a very good permutation generating code

 

http://www.merriampark.com/perm.htm

 

You only need to write the part which generates p partition of n and append the arrays. If you do a permutation, make sure you permute integers and not its String form.  For example, better to permute integer 10 versus String "10".  Since "10" is a string of two characters.  So if it's permuted it will come out as "1" and then "0" and not "10".  This would mess up the permutation.

Your program should first ask:

What is n=?

What is p=?

Also the full results might overrun the DOS Prompt screen.  So in addition of displaying results to the DOS screen, you might also write the results to a text file  also.  So you can use PrintStream (new FileOutputStream).

 

Example 1. For example n=4, p=3

The partition (2,1,1) is good.

A1

2

1

1

A2

2+1

1+1

3

2

A3

2+1+1

4

Create B

2

1

1

3

2

4

After sorting

1

1

2

2

3

4

 

Therefore (2,1,1) is good

  For n=5,p=3

The partition (2,2,1) is good.

 

Example 2.n=6,p=3.

(1,2,3) is not good but (1,3,2) is good.

The partition (1,2,3) is not good.

A1

1

2

3

A2

1+2

2+3

3

5

A3

1+2+3

6

Create B

1

2

3

3

5

6

After sorting

1

2

3

3

5

6

You have skipped “4”. Therefore (1,2,3) is  not good.

 

Example 3.

The partition (1,3,2) is good.

A1

1

3

2

A2

1+3

3+2

4

5

A3

1+3+2

6

Create B

1

3

2

4

5

6

After sorting

1

2

3

4

5

6

 

Therefore (1,3,2) is good

 

Example 4. Consider n=10 and p=4

If we have a partition (1,4,2,3), it is not good.For your program will generate

A1

1

4

2

3

A2

5

6

5

A3

7

9

A4

10

B

1

4

2

3

5

6

5

7

9

10

After sorting B we have the array

1

2

3

4

5

5

6

7

9

10

 

The array skipped “8” so (1,4,2,3) is not good.

 

Output format

n=6, p=3

Good permutations are:

(1,3,2)

A1

1

3

2

A2

1+3

3+2

4

5

A3

1+3+2

6

Create B

1

3

2

4

5

6

After sorting

1

2

3

4

5

6

 

(2,3,1)

A1

2

3

1

A2

2+3

3+1

5

4

A3

2+1+3

6

Create B

2

3

1

5

4

6

After sorting

1

2

3

4

5

6

 

Total number: 2.

Time spent on this task: 34 microsecond.

 

Other advices: The program will be examined on functionality (whether it works) and the quality of the code. Comments and indents are important for making your program easy to read. Your program will be easier to understand and to change if you decide to change it later.

(a) Write comments to explain what your program is doing and why.

(b) Use descriptive names for your variables.

Code should be organized and documented as well as neat. Documentation should include name and email address at the top.

 

Turn in Thursday (2/26/2004) two separate envelopes containing the following:

- A report-describing what you discovered from the program

(1) For p=3, what is the maximum n which will produce good permutations.

(2) Do this for p=4,5,6,7,8.

In your report you should mention what kind of permutation algorithms and sorting algorithm you are using. Also the sources of your references (for example: www. Xyz.com/lee/permutation/partition) .

- Two diskettes with both source code and executable.

- Complete source code in a hard copy printout.

- Complete six cases outputs in a hard copy printout.

Turning in homework directions:

From now on you are going to be required to make a ms-dos batch file that must be included with your program, the purpose of this is to have a shortcut that runs your program. On your disk drive make a file called program?.bat where the “?” is the homework assignment.

 

Inside that document you must include the following:

::

:: these are comments

:: Assignment #?

:: Name=

:: Date=

:: Class=

:: Section=

::

@ECHO OFF

:: compiles the java file

javac *.java

 

::  Make sure “Program1” points to the class name that starts your program

java -classpath "" Program1

 

pause

 

That is it.

For more information on Dos Batch files refer to:

http://www.chebucto.ns.ca/~ak621/DOS/BatBasic.html

Grading

To receive a better grade, you have to add features that increase functionality and/or presentation. Here are some examples:

·        A mechanism for changing the speed of the demo when run in continuous mode.

·        An option to use different types of data.

·        Fancier displays, including better graphics, pretty colors, or a more visually stimulating demo.