California State University, Dominguez Hills
Department of Computer Science
Spring 2005
CSC121A Lab 14: Array and Search
Goals:
1. Understand array, index, and access to array elements
2. Be able to program with array
3. Understand the control structure of using array
4. Understand search
Exercises P13.11 on Page 553
Write a program that produces random permutations of the numbers 1 to 10. To generate a random permutation, you need to fill an array with the numbers 1 to 10 so that no two entries of the array have the same contents. You could do it by brute force, by calling Random.nextInt until it produces a value that is not yet in the array. Instead, you should implement a smart method. Make a second array and fill it with the numbers 1 to 10. Then pick one of those at random, remove it, and append it to the permutation array. Repeat ten times. Implement a class PermutationGenerator with a method
int[] nextPermutation()
Requirements:
1. Create a project CSC121ALab14 in BlueJ.
2. Create a class PermutationGeneratorTest in the project, and type the source code that contains the main in it. Your main method should read a number n, create an object of PermutationGenerator (see 3), call the method nextPermutation() (as below) to produce a permutation of numbers 1 to n, and print out the permutation.
3. Create a class PermutationGenerator in the project, and type the source code as described in Exercise P13.11. However, you should implement the smart method, instead of the brute-force method. Without using the constant 10, your program should produce random permutations of numbers 1 to n. The constructor accepts the parameter n, and the method int[] nextPermutation() produces the random permutations.
4. Compile all source code and run the byte code.
5. Your source code documentation must follow the instructions of Chapter 2.8, pages 54-56. Be advised to briefly comment all classes, constructors, and methods.
Implementations:
1. The class PermutationGenerator: Brute-force
import java.util.Random;
/**
* Permutate numbers between 0 and n
* @author <J. Han>
* @date <4/20/2005>
*/
public class PermutationGenerator {
/**
* Field
*/
private int permut[];
/**
* Constructor
* @param int the number of numbers in the permutations
*/
public PermutationGenerator(int n) {
permut = new int[n];
}
/**
* Generate a permutation
* @return int[] the permutation of numbers 1 to n
*/
public int[] nextPermutation() {
// Create a random generator
Random generator = new Random();
int n = permut.length;
for (int i=0; i<n; i++) {
while (true) {
// Generate a random number between 1 and n
int nextRandomNumber =
generator.nextInt(n)+1;
boolean next = true;
for (int j=0; j<i; j++)
if (permut[j]==nextRandomNumber) {
next = false;
break;
}
if (next) {
permut[i] = nextRandomNumber;
break;
}
}
}
return permut;
}
}
2. The Test class: PermutationGeneratorTest
/**
* PermutationGenerator test
*/
public class PermutationGeneratorTest {
public final static void main(String[] args) {
int n = Integer.parseInt(args[0]);
PermutationGenerator generator =
new PermutationGenerator(n);
int[] p = new int[n];
for (int i=0; i<n; i++)
{
System.out.println(“The permutation “ + (i+1) +
“ of numbers between 1 and " + n +": ");
p = generator.nextPermutation();
for (int i=0; i<n; i++)
System.out.print(p[i] + ", ");
System.out.println("");
}
}
}
Exercise:
Rewrite the method int[] nextPermutation() of the class PermutationGenerator such that it implements the smart method described in Exercise P13.11, instead of the brute-force method as above.