cresjoy cresjoy - 4 months ago 10
Java Question

Understanding Filling array with Random Numbers (Big Java Ex 7.4)

Problem Statement


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


I'm having some trouble understanding what the question is saying.

My interpretation is that we need to put the numbers 1-10 in array, given some random numbers which can range from one to ten.

The way I would solve this is by simply adding to an array and doing a loop and just check whether the next random number is already within the array. However as per the question, this is considered "brute force"

I'm not exactly sure what my book is saying by implementing a second array. If I make a second array won't I still have to check whether something is in the array?

My Attempt
First I'm just trying to put 10 random numbers into an array, and ignoring the part about that they have to be distinct. Heres what i have

private int[] arr;
private Random randNum;

public seq()
{
randNum = new Random();
arr = new int[10];
}

public int getRandNum()
{
int newNum = randNum.nextInt(10)+1;
return newNum;
}

public int [] filledArr()
{
for (int i = 0 ; i<arr.length; i++)
{
arr[i] = getRandNum();
}
return arr;
}


The problem with this is that I would have to call
getRandNum()
10 times to get 10 different numbers, and then call
filledArr
to put it inside. This is ALOT of typing. Is there a better way? I guess I could also make a for loop inside the main, and do this? This seems horribly inefficient.

Thanks for any Advice

Another
Attempt


class seq
{
private int[] arr;
private int[] filledArr;
private Random randNum;

public seq()
{
randNum = new Random();
arr = new int[10];
filledArr = new int[10];
}

public int [] generateNewArr()
{
for(int i = 1; i< 11 ; i++)
{
filledArr[i] = i;
}
return filledArr;
}

public int [] newArr()
{
for(int i=1; i < 11 ; i++)
{
int newRandNum = //RANDOM NUMBER IN filledArr;
arr[i] = newRandNum;
// REMOVE that random number from filledArr
}
}

}


ATTEmPT WITH ARRAYLISTS

import java.util.Random;
import java.util.ArrayList;
class seq
{
private ArrayList<Integer> arrListOne;
private ArrayList<Integer> arrListTwo;
private Random num;
public seq()
{
num = new Random();
arrListOne = new ArrayList<Integer>(10);
arrListTwo = new ArrayList<Integer>(10);
}
public ArrayList getFilledArr()
{
for(int i = 1; i < arrListOne.size()+1 ; i++)
{
arrListOne.add(i);
}
return arrListOne;
}
public ArrayList randNewArr()
{
for(int i = 0 ; i < 10 ; i++)
{
int randNum = num.nextInt(arrListOne.size())+1;
arrListTwo.add(arrListOne.get(randNum));
arrListOne.remove(arrListOne.get(randNum));
}
return arrListTwo;
}

public String toString()
{
String output = "The Randomized ArrayList is";
output+=arrListTwo;
return output;
}
}

public class Sequence
{
public static void main(String [] args)
{
seq seqObj = new seq();
seqObj.getFilledArr();
seqObj.randNewArr();
System.out.println(seqObj.toString());
}

}

Answer

The question is simply saying this:

Make an array with numbers 1-10 (doesn't have to be randomly ordered). Then generate a random number between 1-10 and pick the number and remove that index from the array you created earlier.

A rough implementation would be:

ArrayList nums = new ArrayList<Integer>(); // The arraylist with numbers from 1-10
for(int i = 1; i < 11; i++;)
    nums.add(i);

Random r = new Random();
int x = r.nextInt(10);

int[] finalNums = new int[2];
finalNums[0] = nums.get(x);
nums.remove(x); // Remove the number at this index so it won;t be picked up again

x = r.nextInt(9); // Since we removed one index from arraylist, so total elements are now nine instead of 10.
finalNums[1] = nums.get(x);
nums.remove(x);

So what's the difference? In this approach, you are sure that it won't pick same number twice. WHy? Because you remove the number as soon as you pick it so it has no change of getting picked up again.

EDIT:

As for your attempt with ArrayList where you have asked what you write in the main block, you simply have to call the two methods you created in class in order. It could either be in main block:

public class Sequence
{
    // You need one main method atleast to run the code
    public static void main(String[] args){
        seq seqObj = new seq();
        System.out.println(seq.getRandomArray());
    }
}

Or you could also call these methods in seq class' constructor:

public seq()
{
    randNum = new Random();
    arr = new int[10];
    filledArr = new int[10];
    this.getFilledArr();
    this.randNewArr();
}

Another thing to note, your method to display output of ArrayList is not okay. A little correction to your code:

import java.util.Random;
import java.util.ArrayList;
class seq
{
    private ArrayList<Integer> arrListOne;
    private ArrayList<Integer> arrListTwo;
    private Random num;

    public seq()
    {
        num = new Random();
        arrListOne = new ArrayList<Integer>();
        arrListTwo = new ArrayList<Integer>();
        getFillerArr();
        randNewArr();
    }

    // You dont have to return ArrayList here
    public void getFilledArr()
    {
        for(int i = 1; i < 11 ; i++)
        {
            arrListOne.add(i);
        }
    }

    // You dont have to return ArrayList here
    public void randNewArr()
    {
        for(int i = 0 ; i < 10 ; i++)
        {
            int randNum = num.nextInt(arrListOne.size())+1;
            arrListTwo.add(arrListOne.get(randNum));
            arrListOne.remove(arrListOne.get(randNum));
        }
    }

    // A method that returns you random array list so you can easily use it following rules of encapsulation
    public ArrayList<Integer> getRandomArray() {
        return this.arrListTwo;
    }
}

public class Sequence
{
    public static void main(String[] args){
        seq seqObj = new seq();
        System.out.println(seq.getRandomArray());
    }
}

EDIT #2:

For your problem of negative bound exception, This is how your code should be:

    public seq()
    {
        num = new Random();

        // Do not try to specify size of Array List here. THey don't have fixed size.
        arrListOne = new ArrayList<Integer>();
        arrListTwo = new ArrayList<Integer>();
        getFillerArr();
        randNewArr();
    }

    public void getFilledArr()
    {
        // Manually iterate for 10 elements.
        for(int i = 1; i < 11 ; i++)
        {
            arrListOne.add(i);
        }
    }

    public ArrayList randNewArr()
    {
        for(int i = 0 ; i < 10 ; i++)
        {
        // Do not add +1 here, actual array size is already 1 less than the size you get from #size() method.
        int randNum = num.nextInt(arrListOne.size());
        arrListTwo.add(arrListOne.get(randNum));
        arrListOne.remove(arrListOne.get(randNum));
        }
        return arrListTwo;
    }

Explanation:

arrListOne = new ArrayList<Integer>(10);

Here you are trying to create an array list of fixed size 10? But ArrayLists do not have a fixed size. So this won't work. Hence your this loop fails too:

public ArrayList getFilledArr()
{
    for(int i = 1; i < arrListOne.size()+1 ; i++)
    {
        arrListOne.add(i);
    }
    return arrListOne;
}

(array list has 0 size, so loop doesn't run).

Hence you get that exception when getting random number.

PS: My bad, been a while since I did java. Somehow I overlooked it while reading that code.

Comments