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 10 times. Implement a class PermutationGenerator with a method

int[] nextPermutation

Complete the following file:


import java.util.Random; /** This class generates permutations of a sequence of integers 1...length. */ public class PermutationGenerator { . . . /** Construct a PermutationGenerator object. @param length the length of the permutations generated by this generator. */ public PermutationGenerator(int length) { . . . } /** Gets the next permutation. @return the array containing the next permutation */ public int[] nextPermutation() { . . . } }

Use the following file:


   This class prints 5 permutations of the numbers 1 through 10.
public class PermutationPrinter
   public static void main(String[] args)
      PermutationGenerator gen = new PermutationGenerator(10);      
      for (int i = 1; i <= 5; i++)
         for (int n : gen.nextPermutation())
            System.out.print(" " +  n);