Lesson 20 - ArrayList

L.A.20.2 - Permutations

page 9 of 9

Assignment:

1. Write a program that produces random permutations of the numbers 1 to 10. "Permutation" is a mathematical name for an arrangement. For example, there are six permutations of the numbers 1,2,3: 123, 132, 231, 213, 312, and 321.

2. To generate a random permutation, you need to fill an ArrayList 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 ArrayList and fill it with the numbers 1 to 10. Then pick one of those at random, remove it, and append it to the permutation ArrayList. Repeat ten times.

Instructions:

1. Declare two ArrayLists

· ArrayList <Integer> randPermutation; ArrayList <Integer> intList;
Declare two Constructors that look like the following:

1) A constructor that takes in one argument that is the size of the array
// a one argument constructor a with a size parrameter

public PermutationGenerator(int lsize){

randSelection = new Random();
listSize = lsize;

intList = new ArrayList( listSize);
randPermutation = new ArrayList(listSize);

}

2)A no argument constructor that sets the defaul permutation to 10
public PermutationGenerator() {
this(10); // this calls the the one argument constructor
}

2. Create a method called nextPermutation() that
1. First fill the ArrayList intList with the numbers 1 to the listSize which is 10 so that no two entries of the array have the same contents. In other words fill up the intList ArrayList with the numbers 1 to 10. (Note the loop starts with 1)
2. Then pick a number at random using (using Random.nextInt(int), that removes a number from the intList.
3. Then add and append the random number to the randPermutation ArrayList. This operation is repeated listSize times.
4. The nextPermutation method returns a randPermutaion ArrayList
5. In main you will call nextPermutation method in a loop that prints out the values of the returned randPermutation ArrayList

3. The run output will consist of 10 lists of random permutations of the number 1 to 10. Example output is shown below:

4. Random Permutation List Generator
5.  
6. List 1: 4 6 8 1 9 7 10 5 3 2
7. List 2: 6 8 1 7 3 4 9 10 5 2
8. List 3: 2 4 9 6 8 1 10 5 7 3
9. List 4: 8 5 4 3 2 9 6 7 1 10
10. List 5: 10 3 2 6 8 9 5 7 4 1
11. List 6: 9 10 3 2 1 5 6 8 4 7
12. List 7: 3 8 5 9 4 2 10 1 6 7
13. List 8: 3 2 4  5 7 6 9 8 10 1
14. List 9: 4 1 5 10 8 3 6 2 7 9
List 10: 3 5 2 4 1 7 9 6 8 10

	Contact

	©ICT 2003, All Rights Reserved.