Computer Science Canada

help - stop random number from repeating
Author:  whoareyou [ Sun Jun 12, 2011 6:10 pm ]
Post subject:  help - stop random number from repeating
For a trivia game, I'm trying to create a method that will assign a random value (between 0 and the length of the questions array) so that different questions will appear every time. However, my method still doesn't seem to work and I don't know what I'm doing wrong. It is still repeating questions.

What I think I need is to pass an array with the questions already chosen, and a random number, then I need to check the entire array and see if the the number is there. But if it checks one element and it is the same, it will change, but if at another element the number is the same, it might be different and a random number might be a number that was already chosen previously and the checking of the element has already passed so there is a possibility for numbers to repeat.

I just need some guidance to understand what I'm doing wrong and how to improve the code I already have:

Java:

public static int CheckQuestion (int[] questions, int number)
    {
        int count = 0;
 
        while (count == 0)
        {
            for (int i = 0 ; i < questions.length ; i++)
            {
                if (number == questions [i])
                {
                    count++;
                }
 
            }
 
            if (count > 0)
            {
                number = (int) (Math.ceil (Math.random () * questions.length)) - 1;
            }
 
            else
            {
                break;
            }
        }
        return number;
    }
Author:  ProgrammingFun [ Sun Jun 12, 2011 6:38 pm ]
Post subject:  RE:help - stop random number from repeating
Originally initialize the whole array as a negative number. After this, generate random numbers to fill the array but after generating a random number, check it against the whole array before you assign it to a slot in your array.

pseudocode:

initialize whole array as -1

loop
    create integer/double
       generate a random number into this variable

       check variable against whole array
           if variable is unique
               assign into array and exit loop

           else
               retry random number generation
end loop
Author:  whoareyou [ Sun Jun 12, 2011 7:01 pm ]
Post subject:  Re: help - stop random number from repeating
So this is what I did as so far from what it prints to the console screen, different numbers are being generated. However, sometime it just freezes (ex. sometimes it will only generate 5 numbers then freeze, or sometimes even 2 numbers then freeze).

Java:

        int[] randInt = new int [10];

        for (int i = 0 ; i < randInt.length ; i++)
        {
            randInt [i] = -1;
        }

        int number;
        int count = 0;

        for (int i = 0 ; i < randInt.length ; i++)
        {

            while (count != randInt.length)
            {
                number = (int) (Math.ceil (Math.random () * randInt.length)) - 1;

                for (int j = 0 ; j < randInt.length ; j++)
                {
                    if (randInt [j] != number)
                    {
                        count++;
                    }

                }

                randInt [i] = number;
            }

            count = 0;

            c.print (randInt [i] + " ");
        }
Author:  Zren [ Sun Jun 12, 2011 7:29 pm ]
Post subject:  RE:help - stop random number from repeating
Alternatively, you can populate an array with 1 -> n, then swap the numbers around like crazy!
Java:

function swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

for (int i = 0; i < nums.length; i++) // Populate
    nums[i] = i;
for (int i = 0; i < totalSwappage; i++) // Swap the numbers like crazy
    swap(nums, r.nextInt(nums.length), r.nextInt(nums.length));
Author:  ProgrammingFun [ Sun Jun 12, 2011 7:29 pm ]
Post subject:  RE:help - stop random number from repeating
I don't see you validating the number generated against the array because you have only inserted a for loop in between generating and assigning. It does not actually check if each number is unique.

EDIT: Zren's method works too...
Author:  whoareyou [ Sun Jun 12, 2011 7:42 pm ]
Post subject:  Re: help - stop random number from repeating
Unfortunately, Zren's method is using something I haven't learned yet, and this is actually for a summative. But I could use your help as well =).

I rewrote my code and now 10 numbers show up, but some don't change from -1.

Java:

        int[] randInt = new int [10];

        for (int i = 0 ; i < randInt.length ; i++)
        {
            randInt [i] = -1;
        }

        int number;
        int count = 0;

        for (int i = 0 ; i < randInt.length ; i++)
        {
            number = (int) (Math.ceil (Math.random () * randInt.length)) - 1;

            for (int j = 0 ; j < i ; j++)
            {
                if (randInt [j] != number)
                {
                    count++;
                }

            }

            if (count == i)
            {
                randInt [i] = number;
            }

            count = 0;

            c.print (randInt [i] + " ");
        }


Sample output:
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Author:  Tony [ Sun Jun 12, 2011 7:58 pm ]
Post subject:  RE:help - stop random number from repeating
To improve on Zren's idea -- populate an array 1 -> N, and call it "numbers not yet used". Then just sample from there.

Instead of doing 3-assignments swaps that use 2 random numbers, you'll need only a 1-assignment replace using 1 random number (that is, replace item in random index with the last element).
Author:  RandomLetters [ Sun Jun 12, 2011 8:00 pm ]
Post subject:  RE:help - stop random number from repeating
Zren's method is quite simple actually.

There's a built in shuffle method for the Arrays class that randomizes the oder of your arrays.

How it works is also explained in the doc, so you can implement it yourself if you wish.

http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#shuffle(java.util.List)

The advantage is that you don't need to rely on randomly generating until you get the right number, as that can be very inefficient when you're trying to get the last number in a list of 1000.
Author:  whoareyou [ Sun Jun 12, 2011 9:19 pm ]
Post subject:  Re: help - stop random number from repeating
The shuffle method required a list instead of an array. And Zren's method used a function. However, i re-jigged it to get something like:

Java:

        int[] questions = new int [10];

        for (int i = 0 ; i < questions.length ; i++)
        {
            questions [i] = i;
        }

        for (int i = 0 ; i < questions.length ; i++)
        {
            int randomPosition = (int) (Math.ceil (Math.random () * questions.length)) - 1;
            int temp = questions [i];
            questions [i] = questions [randomPosition];
            questions [randomPosition] = temp;
        }

        for (int i = 0 ; i < questions.length ; i++)
        {
            c.print (questions [i] + " ");
        }


I kinda used google to help fabricate this, but i think what's going on is that it's picking 2 random positions and switching them 10 times (the length of the array).
Author:  Insectoid [ Sun Jun 12, 2011 9:39 pm ]
Post subject:  RE:help - stop random number from repeating
You're gonna want to switch more than ten times. A hundred, or a thousand times is far more appropriate.
Author:  RandomLetters [ Sun Jun 12, 2011 10:34 pm ]
Post subject:  Re: help - stop random number from repeating
Would something like this work?
It's late at night so I doubt my thinking Razz
code:

int c = old.length;
int k;
int[] new = new int[old.length];


for(int i = 0; i < new.length; i++) {
     k = this.rand(0, c);  //where rand(a, b) gives a rand integer between a inclusive and b exclusive, so, pick an index at random
     new[i] = old[k];      //take the element from the new index
     c--;                 //reduce the range
     this.swap(old, k, c); //swap old[k] and old[c-1] so that it wont be picked again
}

Edit:
It works! Very Happy

Edit:
If you're allowed to use built in functions, just convert to a list with asList() and then shuffle.

This is quite useless but I'm curious, what about making a comparator that returns a random integer and using sort?
Author:  whoareyou [ Mon Jun 13, 2011 7:15 pm ]
Post subject:  RE:help - stop random number from repeating
@Insectoid - Why do I need to switch it more than 10 times? The for-loop I used does it 10 times because there are 10 elements in the array, so every element is switched.

@RandomLetters - When I tried to use Collections.shuffle, I used Arrays.asList but it gave me an error Neutral. And also, when I import java.util.*, it says that something was already loaded from java.awt Neutral.
Author:  ProgrammingFun [ Mon Jun 13, 2011 7:18 pm ]
Post subject:  Re: RE:help - stop random number from repeating
whoareyou @ Mon Jun 13, 2011 7:15 pm wrote:
And also, when I import java.util.*, it says that something was already loaded from java.awt Neutral.

Why would it say that? You should be able to import any library you want with any other (at a basic level at least).
Author:  whoareyou [ Mon Jun 13, 2011 7:24 pm ]
Post subject:  Re: help - stop random number from repeating
This is the code I'm using from this examplesdepot website:

code:

// Create a list
List list = new ArrayList();

// Add elements to list

// Shuffle the elements in the list
Collections.shuffle(list);

// Create an array
String[] array = new String[]{"a", "b", "c"};

// Shuffle the elements in the array
Collections.shuffle(Arrays.asList(array));


So in order to use ArrayList, I importt java.util.*, then it says, "Type List is imported on demand from java/awt and java/util.".
Then I changed the import to java.util.ArrayList, then it says "you cannot assign a "java.util.ArrayList" expression to a "java.awt.List" variable."

Neutral
Author:  Insectoid [ Mon Jun 13, 2011 7:26 pm ]
Post subject:  Re: RE:help - stop random number from repeating
whoareyou @ Mon Jun 13, 2011 7:15 pm wrote:
@Insectoid - Why do I need to switch it more than 10 times? The for-loop I used does it 10 times because there are 10 elements in the array, so every element is switched.


My bad, didn't see that you were switching elements as you create them.
Author:  whoareyou [ Mon Jun 13, 2011 7:31 pm ]
Post subject:  RE:help - stop random number from repeating
YAY! I was right (H) Very Happy
Author:  Tony [ Mon Jun 13, 2011 7:43 pm ]
Post subject:  RE:help - stop random number from repeating
Except that you don't get an even distribution with this method. That is, some outcomes of this type of a shuffle are more likely than others (ideally they should all be the same). See http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html for a detailed explanation of what is going on.
Author:  RandomLetters [ Mon Jun 13, 2011 8:34 pm ]
Post subject:  Re: help - stop random number from repeating
whoareyou @ Mon Jun 13, 2011 7:24 pm wrote:
This is the code I'm using from this examplesdepot website:

code:

// Create a list
List list = new ArrayList();

// Add elements to list

// Shuffle the elements in the list
Collections.shuffle(list);

// Create an array
String[] array = new String[]{"a", "b", "c"};

// Shuffle the elements in the array
Collections.shuffle(Arrays.asList(array));


So in order to use ArrayList, I importt java.util.*, then it says, "Type List is imported on demand from java/awt and java/util.".
Then I changed the import to java.util.ArrayList, then it says "you cannot assign a "java.util.ArrayList" expression to a "java.awt.List" variable."

Neutral


That's because the awt package has its own List class. Try importing the specific classes that you need from each package. Or http://download.oracle.com/javase/tutorial/java/package/usepkgs.html near the bottom if you actually need to use both.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy