Select from Custom Array without Repeat

Question

I found this great code to pick a random number from a "hat" without repeat:

/* RandomHat
  Paul Badger 2007 - updated for Teensy compile 2017
  choose one from a hat of n consecutive choices each time through loop
  Choose each number exactly once before reseting and choosing again
*/

#define randomHatStartNum 0  // starting number in hat
#define randomHatEndNum 25    // ending number in hat - end has to be larger than start  
#define numberInHat (randomHatEndNum - randomHatStartNum) + 1

void setup()
{
  Serial.begin(9600);
  Serial.println("start ");
}

void loop()
{ // randomHat test
  for (int i = 1; i <= numberInHat; i++) {
    int x = randomHat();
    Serial.print(x);
    Serial.print(", ");
    delay(50);
  }
  Serial.println(" ");
}

int randomHat() {
  int thePick;    //this is the return variable with the random number from the pool
  int theIndex;
  static int currentNumInHat = 0;
  static int randArray[numberInHat];

  if  (currentNumInHat == 0) {                  // hat is emply - all have been choosen - fill up array again
    for (int i = 0 ; i < numberInHat; i++) {    // Put 1 TO numberInHat in array - starting at address 0.
      if (randomHatStartNum < randomHatEndNum) {
        randArray[i] = randomHatStartNum + i;
      }
    }
    currentNumInHat = abs(randomHatEndNum - randomHatStartNum) + 1;   // reset current Number in Hat
    Serial.print(" hat is empty ");
    // if something should happen when the hat is empty do it here
  }

  theIndex = random(currentNumInHat);                  //choose a random index from number in hat
  thePick = randArray[theIndex];
  randArray[theIndex] =  randArray[currentNumInHat - 1]; // copy the last element in the array into the the empty slot
  //                                                     // as the the draw is random this works fine, and is faster
  //                                                     // the previous version. - from a reader suggestion on this page
  currentNumInHat--;    // decrement number in hat
  return thePick;
}

I would like to use a custom array to choose from like so:

char *things[]={
"Thing 1", 
"Thing 2", 
"Thing 3", 
"Thing 4", 
"Thing 5", 
"Thing 6", 
};

Which is quite possible as I use the numbers from to first piece of code to select items from my custom array.

So I have two questions about this:

The first being the code first returns "hat is empty" before the numbers.

start
  hat is empty 11, 24, 17, .......
  hat is empty 4, 19, 23, .......

Is there a way to reverse this?

And secondly, I would like define the randomHatEndNum automatic by the lenght of my custom array, but I have trouble implementing that code. What is the right way to approach this?

Answer 1

The first being the code first returns "hat is empty" before the numbers.

Well, you have to comment out the line

Serial.print(" hat is empty ");

I would like define the randomHatEndNum automatic by the lenght of my custom array,

To get the size of an array, the standard idiom is

const int numberInHat = sizeof(things) / sizeof(things[0]);

I rewrote your sketch.

The idea is use randArray to store all the remaining values to return. Then, randomly pick one value (to return) and replace randArray with -1, which signal that the value has been returned, so don't return it again.

The best for functions returning random values is always work in the range 0..n, and adjust that value in the calling code if you need some other range (like 1..n+1). It's simplier and simplify debugging.

/* RandomHat
  Paul Badger 2007 - updated for Teensy compile 2017
  choose one from a hat of n consecutive choices each time through loop
  Choose each number exactly once before reseting and choosing again
*/

char *things[]={
"Thing 0",
"Thing 1", 
"Thing 2", 
"Thing 3", 
"Thing 4", 
"Thing 5", 
"Thing 6", 
};

const int numberInHat = sizeof(things) / sizeof(things[0]);

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

void loop()
{ // randomHat test
  for (int i = 0; i < numberInHat; i++) {
    int x = randomHat();
    Serial.print(x); Serial.print(" ");
    Serial.println(things[x]);
    delay(50);
  }
  Serial.println("----");
}

int randomHat() {
  int thePick = -1;    //this is the return variable with the random number from the pool
  int theIndex;
  static int left = 0;
  static int randArray[numberInHat];


  if  (left == 0) {                                // hat is emply - all have been choosen - fill up array again
    for (int i = 0 ; i < numberInHat; i++) {    // Put {0, ..., n} into randArray.
        randArray[i] = i;
      }
    left = numberInHat;
  }

  // bEmpty always false at this point.
  while (thePick == -1) {
    theIndex = random(numberInHat);                  //choose a random index from number in hat
    thePick = randArray[theIndex];
   }

  left--;
  randArray[theIndex] =  -1;        // value theIndex is not longer available.
  return thePick;
}