Random Generator w/o Repeats?

Hello,

Is there a way to generate a set of random numbers that don't have any repeats?

Thanks,

Jack

Yes. Measure semiconductor junction noise.

Edit - I see that's not really what you need.

You can just use your own function that compares the newly generated number to the last one, and if they are the same - genertes another one.

You can even make it so that there is still a small chance of getting the same number (in case you wanna make it look more 'random')

YemSalat: You can just use your own function that compares the newly generated number to the last one, and if they are the same - genertes another one.

That won't protect against the second to last, and all previous numbers that have been generated.

A random number generator that eliminates repeats isn't random. What do you intend to do with them?

A pseudo random number generator (at least the shift register kind) presents each value in its modulus uniquely (i.e. one time only during the repeating sequence). So if you can tolerate a very long time between repetition, that will work. Since it completely fills the space of numbers described by the given bits, I don't see how you could complain about that. But it is important to know what the use is.

However, if you truncate values from such a sequence, there will be repeats.

aarg: That won't protect against the second to last, and all previous numbers that have been generated.

Sorry, I think I migth be misunderstanding OP.

jhderms18, do you need a sequence of numbers (e.g. from 1 to n) in random order that are all unique OR do you need it so that the next generated number was never the same as the previous one?

Cause my solution only works in the second case.

How would one do that?

I need numbers 1-8 in a random order without repeats. So the end result would be 8 numbers in total.

One “cute” way, is to start with an array containing the numbers 1 to 8, and randomly swap pairs of numbers. Probably not the most efficient. There is a slight problem with knowing when it is “shuffled enough”.

C++ seems to have random_shuffle()

http://stackoverflow.com/questions/14720134/is-it-possible-to-random-shuffle-an-array-of-int-elements

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // array of numbers 1-8
random_shuffle(&a[0], &a[8]); // pointers to beginning and end of array

Fill an array of 52 elements with the numbers 1 to 52.

Use a random number generator to generate an index between 0 and 51. Return that array element value to the user, and set that array element to -1 or some other value.

Repeat. If at any time the array element is -1, generate another random number, and keep doing so until you get a value which isn't -1.

When you can't find a number in the array that isn't -1, then start again.

If you pick 100 random indexes an can't find a number you haven't used yet, then start at the beginning of the array and return the first unused number that you come to.

Sort of what Michinyon said:

#define VALSWANTED 8

void setup() {
  // put your setup code here, to run once:
  long randomVals[VALSWANTED];
  long rand;
  int count = 0;

  memset(randomVals, 0, sizeof(randomVals));

  Serial.begin(9600);

  randomSeed(analogRead(0));
  while (count < VALSWANTED) {
    rand = random(0, 9);                    // <----- THIS LINE GOT DELETED SOMEHOW???
    if (randomVals[rand] == 0) {
      randomVals[rand] = count + 1;
      count++;
    }
  }
  for (int i = 0; i < VALSWANTED; i++) {
    Serial.println(randomVals[i]);
  }
}


void loop() {

}

@econjack, that code produces no output when I compile and run it.

Also: Fisher Yates shuffle

use randomVals

@aarg: Somehow I manage to delete the most important line in the code! I edited the original post.

Sure, that's the "Monte Carlo" approach. Imagine that the array is large, and already mostly full. In that case, the time taken to find an empty cell (since it's by chance) can be quite long. In fact, there is really no guarantee that it will ever terminate.

@aarg: It works fine here, however, since the array is small and the range is also quite small.

aarg: @econjack, that code produces no output when I compile and run it.

Also: Fisher Yates shuffle

This should be the only answer. The Fisher Yates algorithm is simple (simpler than econjack's solution), fast (O(n) in time complexity), and guaranteed to work correctly.

@christop: Perhaps you could post your implementation.