Random 3 of 6

Anyone have a code snippet for randomly selecting 3 out of 6 elements, no more, no less? For instance, you have 6 LED's and you want to turn 3 of them on... but a different 3 each time through the loop.

This sketch is for a bingo generator, should be relative easy to transform to 3 out of 6.
instead of 90 elements you have 6, and instead f drawing all 90 just draw 3.

//
//    FILE: bingoSequence.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: generate random sequence (optimized)
//    DATE: 2015-11-01
//     URL:
//
// Released to the public domain
//

// seed is missing

int bingo[90];

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  // fill array with values
  for (int i = 0; i < 90; i++)
  {
    bingo[i] = i;
  }
  // swap array values
  for (int r = 0; r < 1000; r++)
  {
    int i = random(90);
    int j = random(90);
    if (i != j)// swap
    {
      int t = bingo[i];
      bingo[i] = bingo[j];
      bingo[j] = t;
    }
  }

  // print 90 bingo numbers
  for (int i = 0; i < 90; ++i)
  {
    if (i % 10 == 0) Serial.println();
    Serial.print(bingo[i]);
    Serial.print("\t");
  }
  Serial.println("\n\nBINGO!!!");
}

void loop()
{
}

your turn,

Thanks for the quick response robtillaart, but “… instead f drawing all 90 just draw 3.” doesn’t offer any randomness of the 3.

Maybe this will help:

void setup() {

  int ledSet[0,0,0,0,0,0];
  int iCount = 0;
  long x = 0;

}

void loop() {

  iCount = 0
  do {
    for(i = 0, i < 6, i++) {
      x = random(0,6);
      if(ledSet[x] = 0) {
        ledSet[x] = 1
        iCount++
      }
    }
  } while(iCount < 4)

}

This works, except it’s bias to the low end. I am looking for something (an algorithm would be nice) that would truly select 3 of the 6 elements randomly.

truly random does not exist as random() is a deterministic function.

you must call randomSeed(nr); to initialize the random generator. By initializing it with an number that is more or less random e.g. analogRead, it appears random.

converting your code to something that compiles gives

int ledSet[6] = {0, 0, 0, 0, 0, 0};
int iCount = 0;
int x = 0;


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

  randomSeed(analogRead(A0)); // often random enough..
  
}

void loop()
{
  iCount = 0;
  do {
    for (i = 0, i < 6, i++)
    {
      x = random(0, 6);
      if (ledSet[x] == 0)
      {
        ledSet[x] = 1;
        iCount++;
      }
    }
  } while (iCount < 4);
}

give it a try. (note that random can cause that there are many loops before you have 3 different numbers.

pr

bingo code changed to 3 out of 6

int leds[6];

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  // fill array with values
  for (int i = 0; i < 6; i++) leds[i] = i;

  // swap array values (can be done more efficient
  for (int r = 0; r < 100; r++)
  {
    int i = random(90);
    int j = random(90);
    if (i != j)// swap
    {
      int t = leds[i];
      leds[i] = leds[j];
      leds[j] = t;
    }
  }

  // print 3 numbers
  for (int i = 0; i < 3; ++i)
  {
    Serial.print(leds[i]);
    Serial.print("\t");
  }
  Serial.println();
}

void loop()
{
}

Sorry for the confusion Rob. I just threw up some code as an example of the concept I was going for. I am fully aware that Random() is not truly random. But as you mentioned, it’s random enough.

Your code randomizes the “contents” of the array (with an anti-bubble sort routine [clever]) and then prints the first 3 elements of the array. I am not looking to randomize either the contents or the order. I need to select random “elements” of the array. Think of it as a Boolean array initialized to zeros, and I need to randomly pick 3 of the 6 elements of the array to set to ones.

Below is some sample code that does compile, with x much more succinctly randomized, and actually works. However, it is verbose, especially when the same element is “randomly” selected over and over, and it has a bias to the lower numbered elements. That’s the main rub. Although, quicker, more streamlined code is a secondary goal as well.

  int dataSet[6];
  int xCount;
  long x;

void setup() {

}

void loop() {

  for (int i = 0; i < 6; i++) { dataSet[i] = 0; }  // Zero out the array.
  xCount = 0;                                            // Reeset the counter.
  randomSeed(millis());                                // Generate new random seed.

  do {
    for(int i = 0; i < 6; i++) {
      x = random(0,6);
      if(dataSet[x] = 0) {                            // If we haven't already set this one...
        dataSet[x] = 1;
        xCount++;
      }
    }
  } while(xCount < 4);                             // Just set 3 of them.

}

Thanks Rob.

Proving that this works, that there is an equal probability of each element winding up picked, is interesting.

const int A = 3;
const int N = 6;
int a[N];

void doPick() {
  // put this bit in setup(), if you can
  for(int i = 0; i<N; i++) a[i] = i;

  for(int i = 0; i<A; i++) {
    int j = i + random(N-i); // random goes from 0 to X-1
    int v = a[i]; a[i]=a[j];a[j]=v;
    Serial.println(a[i]);
  }
}

I like the looks of that Paul. Can't wait to try it tomorrow. Thanks.

micro streamlining

x = random(0,6); ==> x = random(6);

Another doPick() function that keeps the input array intact.

Still a chance for deadlock

//
//    FILE: random324.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: demo
//    DATE: 12-11-2015
//     URL:
//
// Released to the public domain
//

int a[6] = { 1, 2, 3, 4, 5, 6};

int b[3];

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  doPick(a, 6, b, 3);

  for (int i = 0; i < 3; i++)
  {
    Serial.println(b[i]);
  }
}

void loop()
{
}

void doPick(int* in, int size, int* out, int count)
{
  while (1)
  {
    // generate a random selection
    for (int i = 0; i < count; i++)
    {
      int x = random(size);
      out[i] = in[x];
    }
    // test if it is ok
    bool ok = true;
    for (int i = 0; i < count - 1 && ok; i++)
    {
      for (int j = i + 1; j < count && ok; j++)
      {
        if (out[i] == out[j])
        {
          ok = false;
        }
      }
    }
    if (ok) break;
  }
}

A deadlock free solution with bit magic

//
//    FILE: random246.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: demo 3 out of 6
//    DATE: 12-11-2015
//     URL:
//
// Released to the public domain
//

// all integers of 6 bits with 3 bits set
int ThreeOfSix[20] = { 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56 };


void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  int x = random(20);
  for (byte i = 0; i < 6; i++)
  {
    if (ThreeOfSix[x] & (1 << i)) Serial.println(i + 1);
  }
}

void loop()
{
}

Note that this sketch only calls random() once, and is quite fast, printing the numbers is most time consuming

Note it will always print the numbers in a sorted manner; and this trick works if the number of combinations is small.

Related to this thread.

int ThreeOfSix[20] = { 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56 };

Very cute, Rob. Can't you use byte rather than int?

That was my next optimization ;)

Using the binary representation { B0000111, ... } would be self documenting, would be better.

This works because there are (6*5*4)/(3*2*1) = 20 combinations == 20 bytes.

5 out of 20 (15504 combinations) would crash the RAM of an UNO.

One could generate a random permutation and decode that. There are very efficient algorithms to generate the nth permutation of a string. that should also work for a string with 5 ones and 20 zeros.

A non-blocking version could use the shuffle algorithm.

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Shuffle the pin numbers, and then pick the first n that you require.

[quote author=Nick Gammon link=msg=2477861 date=1447458516] A non-blocking version could use the shuffle algorithm.

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle [/quote] This is what my example does, except I stop after the first three.