Random number generation without repetition.

Hi,
I want to generate random number(from 1 to 1000) without repeating .I used random Seed function to generate number and stored in array of size 1000.My code is working in Arduino Mega 2560 but not working in Arduino Nano.I tried two different Nano board and also Proteus simulator.No Result.For smaller array size it is working with NANO board.

Please help with the problem.

This is my code.

int howManyNumber = 999;
const int minRandNumber = 1;
const int maxRandNumber = 1000;
boolean duplicateFound;

void loop()
{
  
int myarray[1000];

for(int counter1 = 0;counter1 < howManyNumber; counter1++)
{
  duplicateFound = true;
  while(duplicateFound == true)
  {
    myarray[counter1] = random(minRandNumber,maxRandNumber);
    duplicateFound = false;


    
    for(int counter2 = 0;counter2 < counter1; counter2++)
    {
      if(myarray[counter1] == myarray[counter2])
      {
        duplicateFound = true;
        duplicateTotal++;
      }
    }
  }
}
Serial.println("Random Generation done");
delay(50);
  
for(int i = 0;i<howManyNumber; i++)
{
  Serial.println(myarray[i]);
  delay(1000);
}

}

2000 bytes of stack space on a Nano?

skc351:
Please help with the problem.

well with a 2kb Ram on a nano 2000 bytes is a bit much leaving only 48 bytes for all the other stuff, but a number between 1 & 1000 is technically speaking only 10 bits, so it could be done in a way more complex way. Though i am wondering what is the purpose ? you check for duplicates as well, so in the end you will have 1000 numbers ranging from 1 to 999 and no duplicates... hmm..

Deva_Rishi:
well with a 2kb Ram on a nano 2000 bytes is a bit much leaving only 48 bytes for all the other stuff, but a number between 1 & 1000 is technically speaking only 10 bits, so it could be done in a way more complex way. Though i am wondering what is the purpose ? you check for duplicates as well, so in the end you will have 1000 numbers ranging from 1 to 999 and no duplicates... hmm..

Thank you for your reply. Got it.I will use Mega.Actually i was building a MP3 player which will randomly play songs.Each time its turned on i don't want repetition. :smiley:

Surely you only need 1000 bits, not 1000 ints?

skc351:
I want to generate random number(from 1 to 1000) without repeating

If after you have generated all but one of the numbers, the last one can only have one result in your scheme, and it cannot be certain and random at same time, unless there is a cat involved somewhere.

1 Like

srnet:
unless there is a cat involved somewhere.

Please do not include cats. They tend to push things off the edge of the flat Earth.

srnet:
If after you have generated all but one of the numbers, the last one can only have one result in your scheme, and it cannot be certain and random at same time, unless there is a cat involved somewhere.

What gets really sticky is sitting in a loop generating random numbers over and over and throwing them away waiting to get the one number of the one track you have left.

There’s a better way.

While your code will technically "work", it is inefficient and will take more time than necessary to complete.

Don't think of it as "generating random numbers without duplicates", think of it as "randomizing the order of a group of numbers". It might seem like a small distinction but it really does change the problem. Making a random number generator that satisfies the first task would be relatively inefficient, but the second task only requires a shuffling algorithm, which is much easier to make.

Fill your array with the numbers 1 -> 1,000 in order, then shuffle it. If you properly implement the shuffling algorithm you will end up with all of the numbers in a random order with no duplicates.

Picking the numbers 1 to 999 in random order on a MEGA:

int numbers[999];
int numbersLeft = 999;


void setup()
{
  Serial.begin(115200);
  while (!Serial);


  // List the numbers 1 through 999
  for (int i = 0; i < 999; i++)
    numbers[i] = i + 1;
}


void loop()
{
  if (numbersLeft > 0)
  {
    // Pick from the remaining numbers
    int r = random(0, numbersLeft);
    Serial.println(numbers[r]);
    numbers[r] = numbers[--numbersLeft];
  }
}

This will fit in a Nano but it WILL become progressively slower. It takes almost two seconds to get to all 999 numbers.

byte chosen[(1000 / 8) + 1]; // Defaults to all 0
int used = 0;

void setup()
{
  Serial.begin(115200);
  while (!Serial);
}

void loop()
{
  // Pick from the remaining numbers
  int r = random(1, 1000);
  boolean alreadyUsed = chosen[r / 8] & (1 << (r % 8));
  if (!alreadyUsed)
  {
    chosen[r / 8] |=  (1 << (r % 8)); // Set the bit
    used++;
    Serial.print(used);
    Serial.print(' ');
    Serial.println(r);
  }
}

Delta_G:
What gets really sticky is sitting in a loop generating random numbers over and over and throwing them away waiting to get the one number of the one track you have left.

Indeed so, and if the number was truely random, it could take an infinte amount of time for that to happen .....

Given the application, a better idea would be to just remember the previous eg 100 songs chosen. This method will also work for an enormous song library.

I assume there will need to be a button press after switch on to ensure a random seed?

srnet:
Indeed so, and if the number was truely random, it could take an infinte amount of time for that to happen .....

It could... but on average it will take n/2 tries for that last number. My sketch did all 999 numbers in under 2 seconds so I don't think it's going to be a big problem.

you might want to check your EEPROM.length() ; i would think a nanos onboard eeprrom would be large enough. you could use it instead of your array. you whould also have the benifit of not hearing repeating songs even after it is turned off.

srnet:
Indeed so, and if the number was truely random, it could take an infinte amount of time for that to happen .....

Ok so if i can forget about the complications of the memory size for a moment. Would w=one prefer to start with all numbers (1-999) in location 1-999, now pick from this amount a number (say for example 259) now swap location 259 with location 999 and pick the next number from location 1-998 ?
Now to store the numbers i'd suggest using 10-bit un-split, this should take 1250 bytes. The location of the byte would be defined as [location+location/4] starting at bit (location%4)*2 and read or write 10 bits fro there.

btw i am still a puzzled as to how you were going to fit the mp3 player into the nano, or do you have a separate device for this ?

johnwasser:
It could... but on average it will take n/2 tries for that last number. My sketch did all 999 numbers in under 2 seconds so I don't think it's going to be a big problem.

on a machine there is no such thing a true random, and yes the time would be technically speaking 'undefined'

Deva_Rishi:
on a machine there is no such thing a true random, and yes the time would be technically speaking 'undefined'

Using pure computer code you are correct. However there are a number of ways that a computer can acquire true randomness from the environment. The best ones will use a Geiger counter and a radioactive element, which is guaranteed by physics to be truly random. Cheaper ones can read atmospheric noise from a microphone or thermal noise from a temperature sensor to seed their random algorithms.

Hmmph. I thought I had written this up somewhere, but I can’t find it.

To “shuffle” N selections, without using storage:

  • pick x, such that 2x > N. Preferably, with 2x “close” to N
  • Implement an x bit maximal length LFSR “pseudo random number generator.” (this generates the numbers from 1 to 2x-1, in an apparently random order (but actually not random at all!), using simple operations.)
  • “Mix” the random number with some constant (say, with an xor) - changing the constant will give you different sequences.
  • if a resulting value is larger than N, reject it and go to the next LFSR output repeating until you get one that “fits.”

LFSR is a fine, web-searchable term. All sorts of advanced math. Also, tables on how to implement for “many” values of x…

So for example, suppose there are 4 songs.
Pick a 3bit LFSR, one of which returns (7 5 4 2 1 6 3) (one at a time.)
Let’s xor with a mixer constant 0 (a no-op)
So, we try and reject 7, try and reject 5, play 4, 2, and 1, try and reject 6, play 3…
If we xor with mixer constant 7, we’ll get 0, 2, 3, 5, 6, 1, 4

Statistically, it’s awful. The end sequence is something 1 of 2x possible permutations, instead of 1 of N! (which will typically be much larger), and isn’t really random at all. But it’s probably good enough for an MP3 player (which is exactly what I was thinking of when I came up with the scheme.)

Semiconductors work way down in the quantum realm, and easily yield random noise.
Many modern microcontrollers will contain a “true random number generator.” This includes the SAM chips used on Arduino Zero and Due.

I found my writeup and code!
Writeup:

I was quite disappointed when my new 5-disk MP3 CD changer wouldn’t
“shuffle” (play songs once each in random order) severals CDs worth of
MP3 songs (say, 100+ songs per CD for each of the 5 CDs…) A bit of
reflection convinced me that the programmers didn’t know how to
maintain a shuffled list of several hundred songs in a microcontroller
whose memory was probably full before they added the mp3 decoder. But
you don’t NEED to maintain such a list just to produce a shuffled
sequence.

The enclosed code in shuffle_lib.c will return a shuffled sequence of any
number of items up to 65535, using only 6 bytes or less of storage. A
pseudo-random number generator (PRNG) can be used to produce a non-repeating
sequence of numbers, but the usual implementation will generate only a
sequence of length 2^N-1 (for an N bit number.) That’s not a problem, you
can just filter out all the numbers that are outside the range of interest.
The other problem with a PRN is that the sequence itself repeats; 12 always
follows 232, or whatever. Since our PRNG is generating a larger range than
we want anyway, this can be fixed by permuting the number somehow before
filtering, using a separate permutation constant. This means that our final
algorithm is something like:

shufflednum(max) = filter(max, permute(prng(randreg), permuteconst));

The code example enclosed uses a standard shift-with-xor-feedback scheme for
the PRNG, simple subtraction for the permutation, and a test against the
maximum as the filter, making it quite fast. (however, it needs to be fast
if the number of items to be shuffled is much smaller than the size of the
PRNG. to get 10 items with a 16 bit PRN, you may end up filtering out 65525
numbers. This can be optimized by using a shorter PRN, of course.) Note
that by changing the PRNG seed, you change the starting position of the
shuffled list, but not the list itself, while changing the permutation
constant results in dramatically different sequences.

Enclosed files:

shuffle_lib.c: library functions in hopefully machine-independent C code
shuffle_test.c: demonstration program, written for unix, tested on Solaris
shuffle_log.c: sample run, demonstrating effects of seed vs permutation
constant changes

Implementation Code:

/*
 * shuffle_lib.c
 * Copyright 2002-2004 by Bill Westfield
 *
 * An algorithm for producing a random sequence from N items using minimal
 * storage (32 bits)  The sequence will not repeat items, but can be repeated
 * overall by using the same seeds and offsets.
 */

/*
 * internal storage for the shuffle algorithm
 * These are supposed to be 16 bits each; keep an eye on your compiler.
 */
static unsigned short randreg;      /* shift register PRN seed */
static unsigned short permutation_constant;  /* constant for permutation */


/*
 * pseudorandom
 * return the next pseudo-random number (PRN) using a standard maximum 
 * length xor-feedback 16-bit shift register.
 * This returns the number from 1 to 65535 in a fixed but apparently
 * random sequence.  No one number repeats.
 * (This is the "standard" linear shift register with xor feedback PRN;
 * other PRN generators could be used.)
 */
static unsigned short pseudorandom16 (void)
{
    unsigned short newbit = 0;

    if (randreg == 0) {
        randreg = 1;
    }
    if (randreg & 0x8000) newbit = 1;
    if (randreg & 0x4000) newbit ^= 1;
    if (randreg & 0x1000) newbit ^= 1;
    if (randreg & 0x0008) newbit ^= 1;
    randreg = (randreg << 1) + newbit;
    return randreg;
}

/*
 * permutate
 * in order to generate multiple pseudorandom seqeunces from a single
 * pseudo-random seqeunce, we (variably) do a 1:1 mapping of the first
 * PRN to a second set.  Subtraction works fine, as would addition, xor,
 * and other possibilities.
 */
static unsigned short permutate (unsigned short input)
{
    return (input - permutation_constant);
}


/**************************************************************************
 *
 * The following functions are the externally visible interface to the
 * shuffle algorithm.
 **************************************************************************
 */

/*
 * shuffle_init
 *
 * set the constants used by the shuffled number generator.
 *
 * Inputs: unsigned short prn_seed - the initial value for the PRN generator
 *         int permutation_const - value for controlling permutation
 *
 * (You can think of these inputs simply as two separate seeds.  However,
 *  changing only the prn_seed may result in sequences that duplicates parts
 *  of other sequences. (that is, if you change only the PRN seed, "1" will
 *  appear at different places in the sequence, but the following number will
 *  always be the same.)
 *
 * Outputs: nothing.
 *
 */
void shuffle_init (unsigned short prn_seed, int permutation_const)
{
    randreg = prn_seed;
    /*
     * Our PRN generator will never produce zero, but the permutation WILL
     * under normal circumstances.  Ensure that we always have "normal
     * circumstances" by disallowing zero...
     */
    if (permutation_const == 0)
    permutation_const == 1;
    permutation_constant = permutation_const;
}



/*
 * shuffle_next(max)
 * Given the number of items, pick an apparently random "next item."
 * Use a pseudo-random number as the basic iterator, but use different
 * PORTIONS of the pseudo-random seqeunce, and skip values that are out
 * of range.
 *
 * Returns values in the range of 0..(max-1)
 */

unsigned short shuffle_next (int max)
{
    unsigned short result;

    do {
    result = permutate(pseudorandom16());
    } while (result >= max);
    return result;
}

Test code (for unix, not for Arduino…):

/*
 * Shuffle_test.c
 * Copyright 2002-2004 by Bill Westfield
 *
 * An algorithm for producing a random sequence from N items using minimal
 * storage (32 bits)  The sequence will not repeat items, but can be repeated
 * overall by using the same seeds and offsets.
 *
 * This is a demonstration program that excercises the library in shuffle.c
 */


#include <stdio.h>

extern unsigned short shuffle_next(int max);
extern void shuffle_init(unsigned short prn_seed, int permutation_constant);


void test ()
{
    int i;                /* Loop counter */
    int howmany;            /* How many numbers to shuffle */
    unsigned short rnd;            /* "this" random number */
    int offset, seed;            /* seeds for the generator */

    do {
    /*
     * input data for demonstration
     */
    printf("howmany, offset, seed\n");
    scanf("%d %d %d", &howmany, &offset, &seed);
    if (howmany <= 0)
        break;

    /*
     * Initialize the shuffle mechanism
     */
    shuffle_init(seed, offset);

    /*
     * Get and print the requesting number of shuffled numbers
     */
    printf("\nhowmany = %d,   Offset = %d, seed = %d\n",
           howmany, offset, seed);
    for (i=0; i < howmany; i++) {
        rnd = shuffle_next(howmany);
        printf("%5d", rnd);
        if (i % 15 == 14) {
        printf("\n");
        }
    }
    printf("\n");
    printf("\n--------------------------------------------------------\n\n");
    } while (1);
}

main ()
{
    test();
}

(no, don’t tell me how old you were in 2002. Sigh.)