CODEWITHSUNDEEP
c++arrayssortingarduino
Marcal
Marcal

Reputation: 1371

Populating array with unique int

I have an Arduino sketch which generates random numbers. I need to populate an array with 5 unique generated numbers. In order to do that inside the loop() I did the following:

  for (int i=0; i<5; i++){

number=mappedForNumber(50);

if (isUnique(number)==true){

 numbers[i]=number;

}

}

where number is a global int and numbers is an array, also declared globally at the top of the sketch

the function "isUnique" is as follows:

bool isUnique (int foo){

  bool pepe=true;

   int sizeOfNumbers=sizeof(numbers)/sizeof(numbers[0]);
    
    for (int i=0; i<sizeOfNumbers; i++){

      if (numbers[i]==foo){

        pepe=false;
        break;
      }

    }

  
  return pepe;
  }

When I check the results, it doesn't really work. If I generate say 30 arrays and I print them on the serial monitor, there is always some of the arrays with duplicated numbers.

I haven't coded for a long while and I'm super rusty. Any help would be appreciated. Thanks in advance!

Upvotes: 0

Views: 213

Answers (2)

JohnFilleau
JohnFilleau

Reputation: 4288

I would use a truncated Fisher-Yates algorithm to do this, assuming you need to select sets of five numbers often.

Given a deck of "cards" labeled from 1 to 50, you shuffle your deck, and draw the top five cards. Use them for whatever you want.

However, since you only ever need five, you just need to shuffle the "top five". This is the "truncated" part of Fisher-Yates. Iterate from the end of the deck down five cards and select five cards below that card (including that card) to swap with that one.

Then when you need five more random numbers, shuffle again.

// swaps two integers
void swap(int& a, int& b) {
  int temp = a;
  a = b;
  b = temp;
}

// returns a pointer to an array of ints randomly
// selected between consecutive values in [1, 50]
// num_ints_requested must be <= the size of the deck
const int* ShuffleRandomInts(int num_ints_requested) {
  constexpr int kNumInts = 50;
  static bool initialized = false;
  static int deck[kNumInts];

  if (!initialized) {
    for (int i = 0; i < kNumInts; ++i) {
      deck[i] = i + 1;
    }
    initialized = true;
  }

  // do the truncated shuffle
  for (int i = kNumInts - 1; i >= kNumInts - num_ints_requested; --i) {
    int j = random(0, i);
    swap(deck[i], deck[j]);
  }

  return &deck[kNumInts - num_ints_requested];
}

void loop() {
  // do work
  ...

  // get 5 random numbers between 1 and 50
  // and do something with them
  const int* numbers = ShuffleRandomInts(5);
  DoSomethingWithFive(numbers);

  // get 10 random numbers between 1 and 50
  // (this invalidates the previously selected numbers)
  numbers = ShuffleRandomInts(10);
  DoSomethingWithTen(numbers);

  // do other stuff
  ...
}

If you need to use one set of randomly selected numbers after generating another set of randomly selected numbers, then copy those numbers to a new array before reshuffling.

We return a pointer to const int so that you don't accidentally modify the deck after returning it. To extend the shuffled deck analogy, this would be like dealing five cards to somebody, and having them draw on the cards with a marker before handing them back to you to shuffle again. You don't want that, so you specify that you can't modify the numbers after returning them.

(If you need to modify them, you have to copy them to a non-const int or non-const int array).

Upvotes: 0

Aleksandr
Aleksandr

Reputation: 116

You are using a for loop to populate your numbers array. This for loop will populate the selected index with a number if it is unique and not change the data inside the index if it isn't.
To fix your code:

int i = 0;
int number;
while(i < 5)
{
  number = mappedForNumber(50);
  if (isUnique(number) == true)
  {
    numbers[i]=number;
    i++;
  }
}

Upvotes: 2

Related Questions