USE JAVA. Write a program that produces random permutations of the numbers 1 to

Question

USE JAVA.

Write a program that produces random permutations of the numbers 1 to 10. (Note: “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.

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 smarter 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 permutationArrayList. Repeat ten times.

Instructions:

Turn in your source code and a printed run output.

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

Random Permutation List Generator

List 1: 4 6 8 1 9 7 10 5 3 2
List 2: 6 8 1 7 3 4 9 10 5 2
List 3: 2 4 9 6 8 1 10 5 7 3
List 4: 8 5 4 3 2 9 6 7 1 10
List 5: 10 3 2 6 8 9 5 7 4 1
List 6: 9 10 3 2 1 5 6 8 4 7
List 7: 3 8 5 9 4 2 10 1 6 7
List 8: 3 2 4 5 7 6 9 8 10 1
List 9: 4 1 5 10 8 3 6 2 7 9
List 10: 3 5 2 4 1 7 9 6 8 10

Explanation / Answer

ANS;

This is pretty simple. You just do precisely what the second paragraph says.

First make a list of the numbers we are going to permute.

ArrayList<Integer> unused = new ArrayList<Integer>();
for (int num = 0; num < size; num++) {
// Add the next number to the unused set.
unused.add(num+1);
}

Here I add num+1 because the loop is zero-based (so it runs from zero to nine) but I want the numbers to be one-based. I could have written the loop that way:

for (int num = 1; num <= size; num++)

But I didn't. :-)

Anyway, now I need to generate the permutation. That's easy; just pick a random entry in the unused array, add it to the permutation, and remove it from the unused array.

ArrayList<Integer> perm = new ArrayList<Integer>();
for (int num = 0; num < size; num++) {
int pos = rand.nextInt(unused.size());
perm.add(unused.get(pos));
unused.remove(pos);
}

That's slightly inefficient; I don't need to generate a random number the last time through. I can replace this with the following code.

ArrayList<Integer> perm = new ArrayList<Integer>();
for (int num = 1; num < size; num++) {
int pos = rand.nextInt(unused.size());
perm.add(unused.get(pos));
unused.remove(pos);
}
perm.add(unused.get(0));

Note I modified the starting index to be one, so the loop runs one less time. Then I just take the single left over value and add it to the permutation. This makes the case of size=0 not work... but do you really care?

Here's a complete solution, along with a main method to test it.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
public class PermutationGenerator {
public static void main(String[] args) {
PermutationGenerator pg = new PermutationGenerator(10);
for (int i = 0; i < 10; i++) {
System.out.println(pg.nextPermutation())...
}
}
private int size;
private Random rand = new Random();
public PermutationGenerator(int size) {
this.size = size;
}
public ArrayList nextPermutation() {
// Make a list of the numbers we are going to permute.
ArrayList<Integer> unused = new ArrayList<Integer>();
for (int num = 0; num < size; num++) {
// Add the next number to the unused set.
unused.add(num+1);
}
// Now generate a permutation.
ArrayList<Integer> perm = new ArrayList<Integer>();
for (int num = 0; num < size; num++) {
int pos = rand.nextInt(unused.size());
perm.add(unused.get(pos));
unused.remove(pos);
}
// Return the result.
return perm;
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.