Algorithm for finding random and unique number in a range

Question

I want to know an algorithm to find unique random number which is non repeatable. Every time when I call that in program should be give a unique and random number which is not given before by that algorithm. I want to know because some time in a game or app this kind of requirements are came.

For ex. In a game I have created some objects and save all them in a array, and want to retrieve them by randomly and uniquely and not want to delete from array. This is just a scenario.

I have tried some alternative but they are not good performance wise, never got answer of this question.

How it is possible programmatically?

Thanks in advance.

tldr; a simple approach that works for many situations is to generate and shuffle a set of values, then take the first n (as needed) values - i.e. just like in a powerball drawing — user2864740, May 21 '14 at 07:19
http://stackoverflow.com/a/196022/2864740 , http://stackoverflow.com/a/375361/2864740 , http://stackoverflow.com/a/18326357/2864740 etc — user2864740, May 21 '14 at 07:22

score 1 · Answer 1 · edited May 23 '17 at 11:57

1

Below code generates unique random numbers from 1-15. Modify as per your requirement:-

public class Main
{
     int i[]= new int[15];
        int x=0;
        int counter;

     public int getNumber()
     {
          return (int)((Math.random()*15)+1);
     }
     public int getU()
     {
            x = getNumber();
            while(check(x))
            {
                x = getNumber();
            }
            i[counter]=x;
            counter++;
            return x;
     }
        public boolean check(int x)
        {
            boolean temp = false;
            for(int n=0;n<=counter;n++)
            {
                if(i[n]==x)
                {
                    temp = true;
                    break;
                }
                else
                {
                    temp = false;
                }
            }
            return temp;
        }
     public static void main(String args[])
     {
          Main obj = new Main();

          for(int i=0;i!=15;i++)
          {
               System.out.println(obj.getU());
          }
     }
}

for more info see below links :-

https://community.oracle.com/message/4860317

Expand a random range from 1–5 to 1–7

edited May 23 '17 at 11:57

Community

1
1

answered May 21 '14 at 07:17

duggu

37,851
12
116
113

With all those many links and this was the best approach? – user2864740 May 21 '14 at 07:18
@user2864740 did you think this is not a good approach for help ?because if you think then remember in future – duggu May 21 '14 at 07:22
There are much better solutions in at least 2 of the [relevant] links - it might be worthwhile to read them and incorporate the knowledge into a solution, instead of just grabbing (and copying) the first result. – user2864740 May 21 '14 at 07:23
@user2864740 thanks for advice remember in future as well this answer!!! – duggu May 21 '14 at 07:25
1

@Golu thanks, Is this approach is good, considering about performance if we want large number of values, because you use some loops and array to save these values. – Neeraj May 21 '14 at 07:55
@Neeraj this approach good for me at least so you will modify according to your requirement!!! – duggu May 21 '14 at 08:00

Yuriy · Answer 2 · 2014-05-21T07:32:03.743

The best option seems to me is to remove the returned number from the input list.
Let me explain:

Start with the whole range, for example: range = [0, 1, 2, 3, 4]
Toss a random index, let's say 3.
Now remove range[3] from range, you get range = [0, 1, 3, 4]

And so on.
Here is an example code in python:

import random
rangeStart = 0
rangeEnd = 10
rangeForExample = range(rangeStart, rangeEnd)
randomIndex = random.randrange(rangeStart, rangeEnd)
randomResult = rangeForExample[randomIndex]
rangeForExample.remove(randomResult)

score 0 · Answer 3 · answered May 21 '14 at 07:23

This can be achieved in many ways. Here are the two of them(currently on top of my head) :

Persisting the previously generated values.(for range based random no. generation) In this method you generate a random number and store it(either on file or db) so that when you generate next no. you can match it with the previous numbers and discard it if its already generated.
Generating a unique number every-time. (for non-range based random no. generation) In this method you use a series or something like that which can give you unique number, current-time-millisecs for instance.

score 0 · Answer 4 · answered May 21 '14 at 07:26

0

Get count of your array.
Random an index between (0, count).
Retrieve item of index in array.
Remove that item at index.

As I see that you do iOS, I would give an example in objective-C.

NSMutableArray *array = <creation of your array>;

int count = array.count;

while (1) {

    int randomIndex =  arc4random() % count;

    id object = [array objectAtIndex:randomIndex];

    NSLog(@"Random object: %@", object);

    [array removeObject:object];
    count--; // This is important

    if(array.count == 0)
    {
        return;
    }
}

answered May 21 '14 at 07:26

Thanh-Nhon Nguyen

3,402
3
28
41

Thanks but in this approach your objects are deleted from array, I want to use this array on later time also. – Neeraj May 21 '14 at 07:44
@Neeraj If you want to reuse your objects later, so what is the point of `unique`? If that's the case, you could achieve with my approach my copy your `array` to an temporary one. – Thanh-Nhon Nguyen May 21 '14 at 07:46

score 0 · Answer 5 · answered May 21 '14 at 09:20

Here are two options I could think of ..

Using a history-list

1. Keep past picked random numbers in a list

2. Find a new random number

3. If the number exist in history list, go to 2

4. [optional] If the number lower history list randomness, go to 2

5. add the number to the history list

Using jumps

At Time 0: i=0; seed(Time); R0 = random() % jump_limit

1. i++

2. Ji = random() % jump_limit

3. Ri = Ri-1 + Ji

Algorithm for finding random and unique number in a range

5 Answers5