How to create unique random numbers from a given Random generator

Question

Write an efficient algorithm to print the following two outputs

You are given a pre-defined function named getrand100() which returns an integer which is one random number from 1-100. You can call this function as many times as you want but beware that this function is quite resource intensive. You cannot use any other random generator. You canNOT change the definition of getrand100().

int getrand100(){
    Random rand = new Random();
return (1+rand.nextInt(100));      
}

• Output1: Print numbers 1-20 in random order. (Not 20 random numbers)
• Output2: Print numbers 1-200 in random order. (Not 200 random numbers)

Note:

• i. Every number should be printed exactly once.
• ii. There should be no pattern in the numbers listing. List should be completely random
  i.e., all numbers have equal probability appearing at any place.
• iii. You may call getrand100() any number of time to get randomnumber from 1 to 100.
• iv. You cannot use any other random generator function except getrand100().

Answer 1

You could create a list with your value (1 - 20, 1 - 200) and a random number, then sort the list on the random number.

public class RandomListItem
{
    int value;
    int sortindex;

    public RandomListItem(x,y)
    {
        value = x;
        sortindex = y;
    }
}

for(int i = 1; i <= maxvalue; i++)
{
    list.add(new RandomListItem(i, getrand100());
}

This might not be so good for the 200 list, since you can only generate random numbers up to 100. Might want to use getrand100() * getrand100() or something to generate a wider range of random numbers.

Answer 2

The idea is to use the Random generator given to compute the required random numbers.

1) For random numbers 1-20, just divide the 100 numbers equally to represent 1 to 20.

2) To generate 1-200, find the even numbers from 1 to 200 and then add (-1 or 0) to it to get all the numbers from 1 to 200.

import java.util.*;
public class Rand20_200{
   int number20[]=new int[20]; //numbers in random order
   int number200[]=new int[200];

   public Rand20_200(){
    int n=0;
    int ngen[]=new int[20]; //to store which random numbers are generated
    while(n<20){
      int rnd=1 + (getrand100()-1) / 5;
      if (ngen[rnd-1]==0){
        ngen[rnd-1]=1;
        number20[n++]=rnd;
      }
    }
    System.out.println("Random 20 numbers");
    print(number20);

    ngen=new int[200]; //to store which random numbers are generated
    int numoff[]={-1,0}; //offset to add
    n=0;
    while(n<200){
      int rnd=numoff[(getrand100()-1)/50]+ (getrand100()*2);
      if (ngen[rnd-1]==0){
     ngen[rnd-1]=1;
     number200[n++]=rnd;
      }
    }   
    System.out.println("\nRandom 200 numbers");
    print(number200);
   }

   int getrand100(){
    Random rand = new Random();
    return (1+rand.nextInt(100));      
   }

   void print(int arr[]){
     for(int i=0;i<arr.length;i++){
       System.out.print(arr[i]+" ");
     }
   }

   public static void main(String args[]){
     new Rand20_200();
   }

 }

Answer 3

Assuming this is homework, I'll keep the answer terse. :)

Look into the modulus operator %