This site is a testing version, but all data is shared with the live forum.


Raised This Month: $ Target: $400
 0% 

Generate Random Unique Numbers for Any Range


  
 
AlliedModders Forum Index > AMX Mod X > Scripting > Code Snippets/Tutorials
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
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 - 496 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
 

« Previous Thread | Next Thread »


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -4. The time now is 15:25.

DMCA - Archive - Top

Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode