Thread: Generate Random Unique Numbers for Any Range
View Single Post
Author Message
addons_zz
Veteran Member
addons_zz's Avatar
Join Date: Aug 2015
Location: Dreams, zz
Old 12-28-2016 , 21:37   Generate Random Unique Numbers for Any Range
Reply With Quote #1
Generate Random Unique Numbers for Any Range

A closed function, i.e., a stock to generate random unique numbers for any range.

References:
  1. [code] infinity loop
  2. [HOW TO] Retrieve random values from an array without retreiving the same twice
  3. Wikipedia - Time complexity
  4. Wikipedia - Computational complexity theory
  5. Wikipedia - Deferred Procedure Call
  6. STockOverflow - What are the benefits of a Deferred Execution in LINQ?


The Stock Unlimited
Code:
#define MAX_INTEGER  2147483647
#define MIN_INTEGER -2147483648

/**
 * Get unique random numbers between a minimum until maximum.
 *
 * If the `maximum`'s change between the function calls, the unique random number sequence will be
 * restarted to this new maximum value. Also after the maximum value been reached, the random unique
 * sequence will be restarted and a new unique random number sequence will be generated.
 *
 * If your `maximum` parameter value is not 0, you can to reset the sequence manually just to calling
 * this function as `getUniqueRandomInteger( holder )` or using some the `maximum` parameter value.
 * The random generated range is:
 *
 *     minimum <= return value <= maximum
 *
 * 1. Do not forgot the call ArrayCreate() for the `holder` parameter before calling this function,
 *    and to call ArrayDestroy(1) for the `holder` parameter after you finished using this function.
 * 2. Do not change the minimum value without changing at the same time the maximum value, otherwise
 *    you will still get number at the old minimum value starting range.
 * 3. This algorithm complexity is linear `O( n )` for the first call and when the random generated
 *    sequence is restarted. The further function calls has constant `O( 1 )` complexity.
 *
 * @param holder      an initially empty Dynamic Array used for internal purposes.
 * @param minimum     the inclusive lower bound limit, i.e., the minimum value to be sorted.
 * @param maximum     the inclusive upper bound limit, i.e., the maximum value to be sorted.
 * @param restart     if false, the sequence will not be automatically restarted and will to start
 *                    returning the value -1;
 *
 * @return an unique random integer until the `maximum` parameter value.
 */
stock getUniqueRandomInteger( Array:holder, minimum = MIN_INTEGER, maximum = MIN_INTEGER, restart = true )
{
    static lastMaximum = MIN_INTEGER;

    new randomIndex;
    new returnValue;
    new holderSize = ArraySize( holder );

    if( lastMaximum != maximum
        || ( restart
             && holderSize < 1 ) )
    {
        lastMaximum = maximum;
        ArrayClear( holder );

        for( new index = minimum; index <= maximum; index++ )
        {
            ArrayPushCell( holder, index );
        }
    }
    else if( holderSize < 1 )
    {
        return -1;
    }

    --holderSize;

    // Get a unique random value
    randomIndex = random_num( 0, holderSize );
    returnValue = ArrayGetCell( holder, randomIndex );

    // Swap the random value from the middle of the array to the last position, reduces the removal
    // complexity from linear `O( n )` to constant `O( 1 )`.
    ArraySwap( holder, randomIndex, holderSize );
    ArrayDeleteItem( holder, holderSize );

    return returnValue;
}

The Stock Limited
Code:
/**
 * Get unique random positive numbers between 0 until 31. If the `maximum`'s parameter value
 * provided is greater than 31, the generated numbers will not be unique. The range is:
 *
 *     0 <= return value <= maximum <= 31
 *
 * @param sequence     a random positive number to reset the current unique return values.
 * @param maximum      the upper bound limit, i.e., the maximum value to be sorted.
 *
 * @return -1 when there are not new unique positive numbers to return.
 */
stock getUniqueRandomIntegerBasic( sequence, maximum )
{
    static maximumBitField;

    static lastSequence   = -1;
    static sortedIntegers = 0;

    if( lastSequence != sequence )
    {
        lastSequence    = sequence;
        sortedIntegers  = 0;
        maximumBitField = 0;

        for( new index = 0; index < maximum + 1; index++ )
        {
            maximumBitField |= ( 1 << index );
        }
    }

    new randomInteger;

    // Keep looping while there is numbers that haven't yet been selected.
    while( sortedIntegers != maximumBitField )
    {
        randomInteger = random_num( 0, maximum );

        // If the number has not yet been selected yet
        if( !( sortedIntegers & ( 1 << randomInteger ) ) )
        {
            // Set bit on the sortedIntegers bit-field, so the integer will now be considered selected
            sortedIntegers |= ( 1 << randomInteger );

            return randomInteger;
        }
    }

    return -1;
}

The Unit Tests Results:
Spoiler


The Unit Tests Source Code:
Spoiler
Attached Files
File Type: sma Get Plugin or Get Source (full_unit_tests.sma - 502 views - 27.2 KB)
__________________
Plugin: Sublime Text - ITE , Galileo
Multi-Mod: Manager / Plugin / Server
Support me on Patreon, Ko-fi, Liberapay or Open Collective
Last edited by addons_zz; 12-29-2016 at 21:51. Reason: Fixed wrong size calculation
addons_zz is offline