Duplicate problem

[Jon Hughes]

Hi all, i've been given an assignment to do, but i'm stuck already.

Ok basically its a bingo game with no gui, only command line interaction.

At the moment im working on the card generation part, which can be for 2-4 players, here is an example of what it should look like.

**********************************************
* 1 * 11 * 21 * 31 * 41 * 51 * 61 * 71 * 81 *
**********************************************
* 3 * 14 * * 37 * 42 * 53 * 68 * * 90 *
**********************************************
* * 18 * * 38 * * 60 * * * *
**********************************************
* * * * 39 * * * * * *
**********************************************

It has to have 20 random numbers (no duplicates) and 16 blanks in a grid of 9x4.

This is the testing code i've been working with so far so that i know it works before changing it to random values of 1-90.

 
public class Card {
private int checker;
private int checker2;
private int counter;
private int randomNum[] = new int[20];
 
private void setRndNumbers() {

for (int x = 0; x < randomNum.length; x++) {
   randomNum[x] = (int) (Math.random() * 20/*90*/) +1;
   checker = randomNum[x];
   //System.out.println("x = " + x);
   counter = 0;
   for (int y = 0; y <= x; y++) {
      checker2 = randomNum[y];
      //System.out.println("y = " + y);
      if (checker2 == checker1) {
         counter++;
         System.out.println("counter = " + counter);
         if (counter > 1) {
            System.out.println("randomNum" + x + " was " + randomNum[x]);
            randomNum[x] = (int) (Math.random() * 20) +1;
            System.out.println("randomNum" + x + " is now " + randomNum[x]);
            checker2 = randomNum[x];
            counter--;
            }
         }
      System.out.println(randomNum[x]);
      }
   }
}
}

But cant get it to work quite right, i think i might need a set or sortedset, but i cant figure out how to correctly put in primatives and then get them out etc.

Any help is very much appreciated!

[Sayed Ibrahim Hashimi]

But cant get it to work quite right, i think i might need a set or sortedset, but i cant figure out how to correctly put in primatives and then get them out etc.

If you want to add primitives to those data structures then you first need to wrap them up into an object. So if you are using ints then use the Integer class to do this, for double use Double, for boolean use Boolean. Here is an example

        int myInt = 5;
        //wrap the int into an Object
        Integer wrappedInt = new Integer(myInt);
        Set mySet = new TreeSet();
        //add it to the set
        mySet.add(wrappedInt);
        
        //get the int back
        Iterator setIter = mySet.iterator();
        while( setIter != null && setIter.hasNext() )
        {
            Integer current = (Integer)(setIter.next());
            int theInt = current.intValue();
            System.out.println("Current int: " + theInt);
        }

Hope this helps,
Sayed Ibrahim Hashimi

[marc weber]

Here's an interesting algorithm for randomly picking "without replacement" -- that is, avoiding duplicates. Note that this uses a simple array, so no Collections are needed and primitive values can be used without wrapping.

Create an array containing all possible choices.

Set an upper limit denoting the last index of "unpicked" choices. Initially, this will be equal to the last index of the array.

Randomly select an index between 0 and the upper limit.

Return the indexed value as the choice.

Replace the value at that index with the value indexed by the upper limit.

Reduce the upper limit by 1.

Repeat last 4 steps as needed.

Basically, values with an index less than or equal to the limit are unpicked values -- modeling a decreasing pool of valid choices. As soon as a value is picked, it is replaced by an unpicked value, and the acceptable range of index choices is decreased. (If the selected index actually equals the limit, then the value is "replaced" by itself rather than an unpicked value, but that index is immediately excluded from the acceptable range of choices).

In the code below, the number of choices (the size of the array) is equal to the number of picks to illustrate that no duplicates are selected.

class NoDups {
  public static void main(String[] args) {
    // array with values 1-20...
    int[] arr = new int[20];
    for(int x = 0; x < arr.length; x++) {
      arr[x] = x+1;
    }
 
    // set the limit...
    int limit = arr.length - 1;
 
    // randomly pick 20 times without duplicates...
    for(int pick = 1; pick <= 20; pick++) {
      int choice = (int)(Math.random() * limit);
      System.out.println(arr[choice]);
      arr[choice] = arr[limit];
      limit--;
    }    
  }
}

[Jon Hughes]

Thanx for the help

I tried Sayed's code first like this.

  
private void setRndNumbers() {

Set mySet = new TreeSet();

for (int x = 0; x < randomNum.length; x++) {
randomNum[x] = (int) (Math.random() * 20/*90 later*/) +1;
//wrap the int into an Object
Integer wrappedInt = new Integer(randomNum[x]);
//add it to the set
mySet.add(wrappedInt);
}

//get the int back        
Iterator setIter = mySet.iterator();
while( setIter != null && setIter.hasNext() ) {            
Integer current = (Integer)(setIter.next());
int theInt = current.intValue();
System.out.println("Current int: " + theInt);        
}

But i got the following output:
Current int: 2
Current int: 4
Current int: 5
Current int: 6
Current int: 8
Current int: 9
Current int: 11
Current int: 15
Current int: 16
Current int: 17
Current int: 18
Current int: 20

There are no duplicates, but there are also missing numbers which is not what i need.
And im not sure if they should be, but they are sorted, even though i need to kinda do this task later on anyway.


Next i tried marc's code.
It seems to work perfectly for what i need, but just 2 things i dont understand.

1. I dont fully understand the flow of how it works (im still a beginner at java)

2. Why do you put: randomNum[choice] = randomNum[limit]; near the very end?
Before this when it prints out the number, its random with no duplicates, but after it goes over it with the value of limit, im confused there.
But thank you very much for the help


My next tasks for the card will be to:-
Sort the random 20 numbers of 1-90 into blocks of 1-10, 11-20 etc.
Then add each block into a 2 dimensional array of a column for each block with a grid of 9x4.
Then add in the 16 blank spaces.
Then map out a print with the correct values in the correct places.

I hope i can do all this stuff on my own *fingers crossed*

[marc weber]

The trick is maintaining a distinction between index and value.
 
Consider a small example of 5 values.
 
value | 1 | 2 | 3 | 4 | 5 |
index | 0 | 1 | 2 | 3 | 4 |
                          ^
                          limit
 
Suppose we first generate a random "choice" of 2. This is an index, so 
our first value is arr[2] = 3.
 
Now we need to make sure that every value at or below our limit is still
unpicked. Since the value 3 has just been picked, we need to replace it
with an unpicked value. The ideal candidate is the value at arr[limit]. 
Why? Because we are going to lower our limit by one anyway, so we need to 
move that unpicked value into the acceptable range.
 
So arr[choice] = arr[limit] replaces the picked value of 3 with the 
unpicked value of 5. Then we lower the limit by one. Note that in the 
diagram below, our index range is now 0 through 3, and the corresponding 
values are 1, 2, 5, and 4.
 
value | 1 | 2 | 5 | 4 | 5 |
index | 0 | 1 | 2 | 3 | 4 |
                      ^
                      limit
 
Next suppose we pick an index of 1, so our value is 2. After replacing 
values and lowering the limit, we have the following...
 
value | 1 | 4 | 5 | 4 | 5 |
index | 0 | 1 | 2 | 3 | 4 |
                  ^
                  limit
 
Now suppose we pick an index of 2, for a value of 5. This gives us...
 
value | 1 | 4 | 5 | 4 | 5 |
index | 0 | 1 | 2 | 3 | 4 |
              ^
              limit
 
Normally, we would replace the value at the selected index with an 
unpicked value. But in the above case, the randomly picked index happened 
to equal the limit. So the picked value of 5 was replaced with itself. But 
that's okay, because we immediately lowered the limit, which excluded it.

[ March 22, 2005: Message edited by: marc weber ]