5

As a part of my project I need to create non repeating 2 or 3 digit random numbers by giving a set of numbers. I don't want to implement a list or array for that, since I should get 1 random number for each function call.

I tried to do that using SecureRandom class of Java. I got help from some of the sites as well, but I am stuck in between, can we shuffle the VALUES and get it done? But I don't know how that could be done. Can anyone help me? 

import java.security.SecureRandom;
public class RandomNumber {
private static final RandomNumber rnd= new RandomNumber();

    private static final char[] VALUES = new char[] {
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};  
     private static final SecureRandom srn= new SecureRandom();
     public String createID()
     { 
       byte[] bytes = new byte[3]; 
       srn.nextBytes(bytes);

     }
Peter O.
  • 32,158
  • 14
  • 82
  • 96
vidhya
  • 2,861
  • 5
  • 28
  • 28
  • 1
    Is it the digits within the number that should be non-repeating or the resultant 2 or 3 digit numbers? Your shuffling question suggests the former but the latter would sound more like a homework assignment. – Paul Ruane Feb 04 '11 at 11:21
  • Non-repeating as in no subsequent numbers are the same or globally non-repeating? – biziclop Feb 04 '11 at 11:47
  • No..Paul....The digits within the number can be repeated...But the numbers generated for each call should be unique....(eg : 331 is possible ...but 331 should not be generated second time...) – vidhya Feb 04 '11 at 11:49

2 Answers2

12

Fisher-yates shuffle algorithm is the way to go. Its efficient for shuffling. and it works in linear time.

here is algo 

To shuffle an array a of n elements:
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

and the code

for(int i=VALUES.length-1; i>0; i--){
            int rand = (int) (Math.random()*i);
            char temp = VALUES[i];
            VALUES[i] = VALUES[rand];
            VALUES[rand] = temp;
    }
Manoj
  • 5,542
  • 9
  • 54
  • 80
  • Thanks Manoj...but the output of the above program would be an array..right..?then how can i get single value for each function call every time..? – vidhya Feb 04 '11 at 11:46
  • @vidhya: simply put all the ~1000 possible values into an array and shuffle. Then all you have to do is keep a variable to track how many numbers have you produced so far, and keep retrieving the next one in the shuffled array. – R. Martinho Fernandes Feb 04 '11 at 12:15
-2

When Manoj's code iterates it is more likely to swap the lower elements of VALUES[] rather than the higher ones. Ex: For i = 9 there is a 1/10 chance of it swapping with any member of the array (including itself). Then for i = 8 we can never swap with VALUES[9] again because Math.random()*i can only span 0 to 8. This means that the VALUES[9] will equal the original VALUES[9] more often than any other element will equal its respective element (and so on with increasing likelihood of getting swapped as i gets smaller).

I would simply like to correct the above answer to not weight elements of the array:

for(int i=0; i <= VALUES.length - 1; i++){
        int rand = (int) (Math.random()*(VALUES.length-1));
        char temp = VALUES[i];
        VALUES[i] = VALUES[rand];
        VALUES[rand] = temp;

Now the shuffle is performed VALUES.length times (or as many times as you like) and doesn't favor any particular elements of the array.

jambi
  • 1
  • 2
    Actually, your "bugfix" introduces a bug. This is such a common misunderstanding that it is even [discussed](http://en.wikipedia.org/wiki/Fisher-Yates#Implementation_errors) at wikipedia. – meriton May 09 '13 at 10:47