Instructions:

Write a program that produces ten 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, generating random values until you have a value that is not yet in the array. But that is inefficient. Instead, follow this algorithm: Make a second array and fill it with the numbers 1 to 10. Repeat 10 times Pick a random element from the second array. Remove it and append it to the permutation array. A skeleton code is provided for this problem.

Class:

import java.util.Random;

/** This class generates permutations of a sequence of integers 1...length. */ public class PermutationGenerator { private Random generator; private int length;

/** Construct a PermutationGenerator object. @param length the length of the permutations generated by this generator. */ public PermutationGenerator(int length) { // "Seeding" this so testing is deterministic. generator = new Random(42); this.length = length; }

/** Gets the next permutation. @return the array containing the next permutation */ public int[] nextPermutation() { ?????? } }

Tester:

import java.util.Arrays; /** Prints some permutations. */ public class PermutationTester { public static void main(String[] args) { PermutationGenerator gen = new PermutationGenerator(10); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [5, 7, 3, 2, 8, 10, 9, 6, 4, 1] "); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [5, 4, 7, 2, 6, 8, 1, 10, 9, 3] "); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [7, 10, 8, 9, 2, 6, 3, 4, 5, 1] "); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [7, 5, 8, 10, 3, 6, 9, 2, 4, 1] ");

gen = new PermutationGenerator(5); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [2, 3, 4, 5, 1] "); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [5, 4, 3, 2, 1] "); System.out.println(Arrays.toString(gen.nextPermutation())); System.out.println("Expected: [4, 5, 1, 2, 3] "); } }

If everything is expected to be random, how can there be any expected?