4

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?

  • 1
    Use a linear feedback shift register. – whatsisname Oct 20 '16 at 6:47
  • @whatsisname what is that? – John Demetriou Oct 20 '16 at 13:18
  • 1
    See Fisher Yates shuffle – paparazzo Oct 21 '16 at 14:21
12

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.

4

One solution that does not seem to have come up:

In pseudocode

def unique-random-in-range(count, bot, top):
    let B = new List[Integer](count)

    for i = 0 to n - 1:
        B[i] = random-in-range(bot, top - i)

    for gen = 0 to n - 1:
        for gen' = gen + 1 to n - 1:
            if B[gen'] >= B[gen]:
                B[gen']++

    return B

In English:

The basic intuition is this, when we pick out a number we want to be able to skip over it the next iteration. So if we pick 5 out of [1..10] we want the next time to act as if we are picking from [1..10] \ {5}. We could do this by your proposal of checking if we have hit 5 or another already picked number and retrying, but a better way is to do the following: the second time around we pick from [1..9] and represent the fact that 5 has been taken out by incrementing all future picks >= 5.

As an example run, if we want to pick 4 values from [1..10], we might go through the following sequence:

Start:
    B = []

Pick values:
    i = 0:
          pick 5 from [1..10]:
              B = [5]
    i = 1:
          pick 2 from [1..9]:
              B = [5, 2]
    i = 2:
          pick 5 from [1..8]:
              B = [5, 2, 5]
    i = 3:
          pick 3 from [1..7]:
              B = [5, 2, 5, 3]

Normalize:
    i = 0 (B[0] = 5):
         B = [5, 2, 6, 3]
    i = 1 (B[1] = 2):
         B = [5, 2, 7, 4]
    i = 2 (B[2] = 7):
         B = [5, 2, 7, 4]
    i = 3 (B[3] = 4):
         B = [5, 2, 7, 4]

Hopefully this gives some intuition about how it works and why the values are guaranteed to be distinct and in range. (Exercise for the reader: prove this.)

If we let n be the number of desired values and k be the size of the range, this algorithm will have time complexity O(n^2) and space O(n). The shuffle algorithm suggested by Euphoric will have time and space complexity O(k). Therefore you might try this method when n is smaller than sqrt(k) and shuffle otherwise.

  • So basically the reverse of what I said. Instead of store all possible numbers and pick one from that list at random, store all the random numbers I picked so far, and check if I already picked that number before? – John Demetriou Feb 20 '17 at 9:41
  • I've used similar algorithm for the task before. This algorithm very efficient as long as the amount of numbers to pick is fairly small. – COME FROM Feb 20 '17 at 13:59
  • @JohnDemetriou It's not quite checking if you've picked the number before. Rather we work it as if we had the ability to pick from the range minus everything we've picked already. We do this not by relocking, but by shifting our picks up for every previous pick less than or equal to it. The difference is that we never are repicking and we're not checking if we've picked this number before – walpen Feb 20 '17 at 16:35
  • Yeah sorry, I misunderstood it, but basically what you are saying is any number I pick after each number, increment it? e.g. I pick 2 the first time, I pick 5 the second time, the third time I pick 5 again, normalization will make the second 5 a 7? and if I pick again a 3 normalization will make that a 4 because 3>2 but 2<5? – John Demetriou Feb 21 '17 at 14:06
2

Don't use list as O(n) lookup

Use hashset as you get O(1) lookup

Either Add or Remove depending on fraction of the range you are looking for

public static HashSet<int> RandomFromXtoY(int x, int y, int k)
{
    if (x > y)
        return RandomFromXtoY(y, x, k);

    HashSet<int> hs = new HashSet<int>();
    if (k > (y - x + 1))
        return hs;

    Random rand = new Random();
    int next;

    if (k > (y - x) * 2 / 3)
    {
        hs = new HashSet<int>(Enumerable.Range(x, y - x + 1));
        while (hs.Count > k)
        {
            next = rand.Next(x, y + 1);  //net max is not inclusive
            hs.Remove(next); //duplicate just fails
            if (next == x)
                x++;
            else if (next == y)
                y--;
        }
    }
    else
    {
        while (hs.Count < k)
        {
            next = rand.Next(x, y + 1);  //net max is not inclusive
            hs.Add(next); //duplicate just fails
            if (next == x)
                x++;
            else if (next == y)
                y--;
        }
    }
    return hs;
}

The above is going to be faster but below is a guaranteed to be O(n + k) where n is the number of elements to select from and k is the number to select. It is based on FisherYate shuffle but it quits the shuffle as soon as it has k elements. The shuffle switches positions so that number is not consider in future random.

public static IEnumerable<int> RandomFromXtoYshuffle(int x, int y, int k)
{
    int n = y - x + 1;
    if (k <= n && k > 0)
    {
        if (x > y)
        {
            int xTemp = x;
            x = y;
            y = xTemp;
        }
        List<int> range = new List<int>(Enumerable.Range(x, n));
        Random rand = new Random();
        for (int i = n - 1; i >= n - k; i--)
        {
            if (n == k)
                yield return range[i];
            else
            {
                int swapIndex = rand.Next(i + 1);  //.net rand max is not inclusive
                yield return range[swapIndex];
                if (swapIndex < i)
                    range[swapIndex] = range[i];
            }
        }
    }
}
1

I would use a set data structure for storing the integers. In a set, all items are unique (at least in Python). So let's say that we have a function

rand_int(y, z): #returns a random integer between y and z

You could do it like this:

x = 10 #number of integers we want to generate
randints = set()

while size(randints) < x:
    randints.add(rand_int(y, z))

Of course, you should check if the range between y and z is big enough to generate x of integers.

EDIT:

Let's say you have a function

rand_choice(list): #Returns a random integer from a list

You could generate a list of numbers between y and z and then perform function rand_choice() x times and save the outputs to another list.

This method should only be used with a relatively small set of integers though.

  • So basically use a HasSet or some sort of it that guarantees uniqueness of resulting list on it's own? – John Demetriou Feb 28 '17 at 13:24
  • Yes, that's the idea. Keep in mind though, that sets are unsorted, but that should't be a problem in your case. – Tomáš Král Feb 28 '17 at 18:16
  • BTW, for Python users: Python random module has a built-in function random.sample(population, k) which selects k elements from population.. Population can be a range object and k is the number of elements. – Tomáš Král Feb 28 '17 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.