Non repeating random numbers in Objective-C

Question

I'm using

for (int i = 1, i<100, i++)
    int i = arc4random() % array count;

but I'm getting repeats every time. How can I fill out the chosen int value from the range, so that when the program loops I will not get any dupe?

Answer 1

It sounds like you want shuffling of a set rather than "true" randomness. Simply create an array where all the positions match the numbers and initialize a counter:

num[ 0] =  0
num[ 1] =  1
: :
num[99] = 99
numNums = 100

Then, whenever you want a random number, use the following method:

idx = rnd (numNums);       // return value 0 through numNums-1
val = num[idx];            // get then number at that position.
num[idx] = val[numNums-1]; // remove it from pool by overwriting with highest
numNums--;                 //   and removing the highest position from pool.
return val;                // give it back to caller.

This will return a random value from an ever-decreasing pool, guaranteeing no repeats. You will have to beware of the pool running down to zero size of course, and intelligently re-initialize the pool.

This is a more deterministic solution than keeping a list of used numbers and continuing to loop until you find one not in that list. The performance of that sort of algorithm will degrade as the pool gets smaller.

A C function using static values something like this should do the trick. Call it with

int i = myRandom (200);

to set the pool up (with any number zero or greater specifying the size) or

int i = myRandom (-1);

to get the next number from the pool (any negative number will suffice). If the function can't allocate enough memory, it will return -2. If there's no numbers left in the pool, it will return -1 (at which point you could re-initialize the pool if you wish). Here's the function with a unit testing main for you to try out:

#include <stdio.h>
#include <stdlib.h>

#define ERR_NO_NUM -1
#define ERR_NO_MEM -2

int myRandom (int size) {
    int i, n;
    static int numNums = 0;
    static int *numArr = NULL;

    // Initialize with a specific size.

    if (size >= 0) {
        if (numArr != NULL)
            free (numArr);
        if ((numArr = malloc (sizeof(int) * size)) == NULL)
            return ERR_NO_MEM;
        for (i = 0; i  < size; i++)
            numArr[i] = i;
        numNums = size;
    }

    // Error if no numbers left in pool.

    if (numNums == 0)
       return ERR_NO_NUM;

    // Get random number from pool and remove it (rnd in this
    //   case returns a number between 0 and numNums-1 inclusive).

    n = rand() % numNums;
    i = numArr[n];
    numArr[n] = numArr[numNums-1];
    numNums--;
    if (numNums == 0) {
        free (numArr);
        numArr = 0;
    }

    return i;
}

int main (void) {
    int i;

    srand (time (NULL));
    i = myRandom (20);
    while (i >= 0) {
        printf ("Number = %3d\n", i);
        i = myRandom (-1);
    }
    printf ("Final  = %3d\n", i);
    return 0;
}

And here's the output from one run:

Number =  19
Number =  10
Number =   2
Number =  15
Number =   0
Number =   6
Number =   1
Number =   3
Number =  17
Number =  14
Number =  12
Number =  18
Number =   4
Number =   9
Number =   7
Number =   8
Number =  16
Number =   5
Number =  11
Number =  13
Final  =  -1

Keep in mind that, because it uses statics, it's not safe for calling from two different places if they want to maintain their own separate pools. If that were the case, the statics would be replaced with a buffer (holding count and pool) that would "belong" to the caller (a double-pointer could be passed in for this purpose).

And, if you're looking for the "multiple pool" version, I include it here for completeness.

#include <stdio.h>
#include <stdlib.h>

#define ERR_NO_NUM -1
#define ERR_NO_MEM -2

int myRandom (int size, int *ppPool[]) {
    int i, n;

    // Initialize with a specific size.

    if (size >= 0) {
        if (*ppPool != NULL)
            free (*ppPool);
        if ((*ppPool = malloc (sizeof(int) * (size + 1))) == NULL)
            return ERR_NO_MEM;
        (*ppPool)[0] = size;
        for (i = 0; i  < size; i++) {
            (*ppPool)[i+1] = i;
        }
    }

    // Error if no numbers left in pool.

    if (*ppPool == NULL)
       return ERR_NO_NUM;

    // Get random number from pool and remove it (rnd in this
    //   case returns a number between 0 and numNums-1 inclusive).

    n = rand() % (*ppPool)[0];
    i = (*ppPool)[n+1];
    (*ppPool)[n+1] = (*ppPool)[(*ppPool)[0]];
    (*ppPool)[0]--;
    if ((*ppPool)[0] == 0) {
        free (*ppPool);
        *ppPool = NULL;
    }

    return i;
}

int main (void) {
    int i;
    int *pPool;

    srand (time (NULL));
    pPool = NULL;
    i = myRandom (20, &pPool);
    while (i >= 0) {
        printf ("Number = %3d\n", i);
        i = myRandom (-1, &pPool);
    }
    printf ("Final  = %3d\n", i);
    return 0;
}

As you can see from the modified main(), you need to first initialise an int pointer to NULL then pass its address to the myRandom() function. This allows each client (location in the code) to have their own pool which is automatically allocated and freed, although you could still share pools if you wish.

Answer 2

You could use Format-Preserving Encryption to encrypt a counter. Your counter just goes from 0 upwards, and the encryption uses a key of your choice to turn it into a seemingly random value of whatever radix and width you want.

Block ciphers normally have a fixed block size of e.g. 64 or 128 bits. But Format-Preserving Encryption allows you to take a standard cipher like AES and make a smaller-width cipher, of whatever radix and width you want (e.g. radix 2, width 16), with an algorithm which is still cryptographically robust.

It is guaranteed to never have collisions (because cryptographic algorithms create a 1:1 mapping). It is also reversible (a 2-way mapping), so you can take the resulting number and get back to the counter value you started with.

AES-FFX is one proposed standard method to achieve this. I've experimented with some basic Python code which is based on the AES-FFX idea, although not fully conformant--see Python code here. It can e.g. encrypt a counter to a random-looking 7-digit decimal number, or a 16-bit number.