Algorithms – Get Unique Random Numbers Within Predefined Limits

algorithms

I am looking for an efficient algorithm to get unique (non repeated) x amount of integer random numbers that are within the y and z limits.

e.g. I want x random integer numbers that are bigger or equal to y, smaller or equal to z and each random number is not repeated.

I came up with two solutions but none of them seems efficient to me.

One solution is on every time I get a random number from my generator I check if that number has been created before. If yes get a new one, if no add it in my list. This solution seems not efficient at all as the amount of needed numbers increases. Also it could theoretically keep looping indefinitely (although not probable).

Another solution I came up with is to keep all the possible numbers in a list and my generator will give me the position to remove a number from the list. Thus I will never have a duplicate number even if the generator will create the same number twice as the number that was there the first time in that position will be removed from the list. But this algorithm also does not seem efficient to me.

Is there a more efficient way to do this that guarantees completion and uniqueness of the random numbers generated?

Best Answer

It highly depend how big range <y,z> is compared to x. If range is huge and x is small, use first algorithm. If they are roughly equal use second.

There is third option is simply taking all numbers in range <y,z>, shuffling them and taking x numbers from beginning. But that is only different version of second algorithm. It will be ineffective if range is big and x is small.

Related Solutions

Algorithms – Generating N Random Numbers Between A and B Summing to X

As said before, this question actually doesn't have an answer: The restrictions imposed on the numbers make the randomness questionable at best.

However, you could come up with a procedure that returns a list of numbers like that:

Let's say we have picked the first two numbers randomly as -0.8 and -0.7. Now the requirement is to come up with 3 'random' numbers that sum up to 2.5 and are all in the range [-1,1]. This problem is very similar to the starting problem, only the dimensions have changed. Now, however, if we take a random number in the range [-1,1] we might end up with no solution. We can restrict our range to make sure that solutions still exist: The sum of the last 2 numbers will be within the range [-2,2]. This means we need to pick a number in the range [0.5,1] to make sure we can reach a total of 2.5.

The section above describes one step in the process.

In general: Determine the range for the next number by applying the range of the rest of the numbers to the required sum. Pseudo-code:

function randomNumbers (number, range, sum) {
  restRange = range * (number - 1)
  myRange = intersection ([sum - restRange.upper, sum - restRange.lower], range)

  myNumber = random(myRange)

  rest = randomNumbers (number-1, range, sum - myNumber)

  return [myNumber, rest]
}

So for the case described above

randomNumbers (3, [-1,1], 2.5)
  restRange = [-1,1] * (3-1) = [-2,2]
  myRange = intersection ([2.5-2,2.5-(-2)], [-1,1]) = intersection ([0.5,4.5],[-1,1]) = [0.5,1]

A quick-and-dirty implementation in Java:

public class TestRandomNumberList
{

    @Test
    public void test()
    {
        double[] numbers = new double[5];
        randomNumbers(numbers, 0, -1, 1, 1);
        assertEquals(sum(numbers), 1.0, 0.00001);
        for (double d : numbers)
        {
            assertTrue(d >= -1 );
            assertTrue(d <= 1);
        }
    }

    private void randomNumbers(double[] numbers, int index, double lowerBound, double upperBound, double sum)
    {
        int next = index + 1;
        if (next == numbers.length)
        {
            numbers[index] = sum;
        }
        else
        {
            int rest = numbers.length - next;  

            double restLowerBound = lowerBound * rest;
            double restUpperBound = upperBound * rest;

            double myLowerBound = Math.max(lowerBound, sum - restUpperBound);
            double myUpperBound = Math.min(upperBound, sum - restLowerBound);

            numbers[index] = random(myLowerBound, myUpperBound);
            randomNumbers(numbers, next, myLowerBound, myUpperBound, sum - numbers[index]);
        }
    }

    private double random(double myLowerBound, double myUpperBound)
    {
        double random = Math.random();
        return myLowerBound + random * (myUpperBound - myLowerBound);
    }

    private double sum(double[] numbers)
    {
        double result = 0;
        for (double num : numbers)
        {
            result += num;
        }
        return result;
    }

}

Algorithms – On-the-Fly Random Partition of a Range of Numbers

I created a partitioning program with space usage O(1) but running time O(N^2). You can find the source code here. In the comments there is a good explanation of the shuffling algorithm used.

The key part of this program is the shuffling step, which is the step that takes O(N^2) time. Doc Brown asked "how can you shuffle N elements in less than O(N) space"? I extracted the shuffling logic and created a separate program which is listed below.

To get the full explanation, please refer to the source code linked above. The following is a brief explanation:

The shuffling function simulates a Fisher-Yates shuffle, where you swap the array[0] with array[r], where r is a random number in the range [0..N-1]. Then you swap array[1] with array[r], where r is a new random number in the range [1..N-1]. You keep moving down the array, swapping random elements, until you reach the end of the array.

To use O(1) space, there is no array. Instead, for each new random element that we select, we need to replay the previous swaps in backwards order in order to figure out where the array element really came from. In essence, we pick a random element, and then we undo the swaps that came before it to determine where the original position of the element was. We can replay the previous swaps by simply reseeding the random number generator back to a previously saved seed.

Edit: After posting this solution, I found this stackoverflow question which lists some better ways to create a permutation of N numbers in constant space. So if you substitute one of those solutions in for my shuffling function, you can do better than O(N^2) time and still use O(1) space.

/* Given a number N, shuffle the elements from 0..N-1 and print them. */
/* This algorithm uses O(1) space but uses O(N^2) time.               */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

static void shuffle(int n);

int main(int argc, char *argv[])
{
    if (argc < 2) {
        printf("Usage: shuffle N\n");
        exit(0);
    }

    shuffle(atoi(argv[1]));
    return 0;
}

static void shuffle(int n)
{
    uint32_t seedOriginal = time(NULL);
    uint32_t seed         = 0;
    int      i            = 0;
    int      j            = 0;
    int      slot         = 0;

    for (i=0;i<n;i++) {
        seed = seedOriginal;
        srand(seed);

        // Skip n-i-1 random numbers.
        for (j=n-i-1;j>0;j--)
            rand();

        // Select an array slot from [i..n-1].
        slot = i + (rand() % (n - i));

        // Find out what that slot corresponds to in the original order.
        // We do this by backtracking through all the previous steps.
        for (j=i-1;j>=0;j--) {
            int r = j + (rand() % (n - j));

            // Every time we see the slot we are looking for, we switch
            // to looking for slot j instead, because at this previous step
            // we swapped array[j] with array[slot].
            if (r == slot)
                slot = j;
        }

        // Slot is now the correct element we are looking for.
        printf("%d\n", slot);
    }
}

Best Answer

Related Solutions

Algorithms – Generating N Random Numbers Between A and B Summing to X

Algorithms – On-the-Fly Random Partition of a Range of Numbers

Related Topic