Raised This Month: $32 Target: $400
 8% 

Generate Random Unique Numbers for Any Range


Post New Thread Reply   
AlliedModders Forum Index > AMX Mod X > Scripting > Code Snippets/Tutorials
 
Thread Tools Display Modes
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 - 489 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
PRoSToTeM@
Veteran Member
PRoSToTeM@'s Avatar
Join Date: Jan 2010
Location: Russia, Ivanovo
Old 12-29-2016 , 09:08   Re: Generate Random Unique Numbers for Any Range
Reply With Quote #2
What is the purpose?
__________________
PRoSToTeM@ is offline
Send a message via ICQ to PRoSToTeM@ Send a message via Skype™ to PRoSToTeM@
gabuch2
AlliedModders Donor
gabuch2's Avatar
Join Date: Mar 2011
Location: Chile
Old 12-29-2016 , 10:09   Re: Generate Random Unique Numbers for Any Range
Reply With Quote #3
Quote:
Originally Posted by PRoSToTeM@ View Post
What is the purpose?
Generating random unique numbers for any range.
__________________
gabuch2 is offline
PRoSToTeM@
Veteran Member
PRoSToTeM@'s Avatar
Join Date: Jan 2010
Location: Russia, Ivanovo
Old 12-29-2016 , 10:39   Re: Generate Random Unique Numbers for Any Range
Reply With Quote #4
Quote:
Originally Posted by Shattered Heart Lynx View Post
Generating random unique numbers for any range.
This is "deferred" random unique numbers. Where can I use them?
__________________
Last edited by PRoSToTeM@; 12-29-2016 at 10:39.
PRoSToTeM@ is offline
Send a message via ICQ to PRoSToTeM@ Send a message via Skype™ to PRoSToTeM@
addons_zz
Veteran Member
addons_zz's Avatar
Join Date: Aug 2015
Location: Dreams, zz
Old 12-29-2016 , 13:26   Re: Generate Random Unique Numbers for Any Range
Reply With Quote #5
Quote:
Originally Posted by PRoSToTeM@ View Post
Where can I use them?
Let us suppose:
  1. You are developing a map chooser plugin.
  2. You need to sort 5 maps from a map list.
  3. You do not want to sort the map map twice for performance questions.

For each map you sort you must to check whether they meet several criteria as:
  1. The map prefix as `de_` must to be unique on the menu.
  2. The map not to be present on the recent maps list.
  3. The map must to to be present to the current hourly blocked list.

So, sorting the same number, on the map index range is processing lost, so would be nice not to sort repeated numbers.

Also the other approach would be to remove all the maps from the map list so we can just sort any.
However this has the following characteristics:
You would have to duplicate the map list as it can be used for other map voting.
You would have to remove the duplicated prefixes from the maps list while duplicating.
You would have to remove the maps from the recent list and hourly list, while duplicating it.

So, I just to choose the first implementation, instead of the second one.
May be the second is trivially better than the first, or otherwise.
Anyways, I already got the second implementation fully working.
So, I would not spend my time doing the second one, if the first one
is not lacking or creating performance problems which cannot be dealt with.
__________________
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 14:03.
addons_zz is offline
PRoSToTeM@
Veteran Member
PRoSToTeM@'s Avatar
Join Date: Jan 2010
Location: Russia, Ivanovo
Old 12-30-2016 , 14:08   Re: Generate Random Unique Numbers for Any Range
Reply With Quote #6
@addons_zz so you are checking the chosen map for your condition after each getUniqueRandomInteger call, aren't you? (while you will not pick 5 appropriate maps)
__________________
Last edited by PRoSToTeM@; 12-30-2016 at 14:16.
PRoSToTeM@ is offline
Send a message via ICQ to PRoSToTeM@ Send a message via Skype™ to PRoSToTeM@
addons_zz
Veteran Member
addons_zz's Avatar
Join Date: Aug 2015
Location: Dreams, zz
Old 12-30-2016 , 18:22   Re: Generate Random Unique Numbers for Any Range
Reply With Quote #7
Yes. But I due other aspects and the performance cost from using this algorithm I removed it because this unique random has linear complexity, by the size of the range at the first call, and is very spend those CPU cycles with that as the map list could be big/worthless.

Currently I to apply simply sorting one random index, and if that map is not available, I increment the ++index instead of sorting a new random. Once the index get at the last position, I start on the first array position and after passed by all maps, I stop the search.

Each time I do a complete loop through all maps, and still not find enough maps due high restrictive settings, I disable one of them, throw on warning at the server console stating I am disabling the X setting due not enough maps to fill the voting, and to start looking for the missing maps to fill the voting. And after disable all restrictions, the voting still not filled, I throw another warning on the server console `log_amx()` stating there was not enough maps and to perform the voting with the found maps, if there are at leas 2 of them.
__________________
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-30-2016 at 18:27.
addons_zz is offline
Reply
AlliedModders Forum Index > AMX Mod X > Scripting > Code Snippets/Tutorials

« Previous Thread | Next Thread »

Thread Tools
Display Modes
Linear Mode Linear Mode

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 13:20.

DMCA - Archive - Top

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