Greetings!
Recently I promised myself that I would make a project that involves arrays and random (two things that give me headache) so I can learn how to use them. A week ago I finished all but one part of the code... The one that involves arrays and random. You see basically I have an array of numbers 1 - 5 and I want the code to print a random number from that array each time the button is pressed. Also the numbers printed shouldn't repeat. I thought that would be easy but then pointers introduced themselves and now I'm depressed. So I stopped trying to do it myself and I looked online for similar codes. And that is how I created this Frankenstein of a code:
#include <Bounce2.h>
Bounce b = Bounce();
int button = 8;
int mySwitchPinArray[] = {1, 2, 3, 4, 5};
int n = sizeof(mySwitchPinArray)/ sizeof(mySwitchPinArray[0]);
void setup() {
Serial.begin(9600);
b.attach(button,INPUT);
b.interval(25);
}
void loop() {
int i;
b.update();
randomisation(mySwitchPinArray, n);
if(b.rose() && i < n){ // wrong stuff here
i++;
Serial.print(mySwitchPinArray[i]);
Serial.print(" ");
}
}
void swap (int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void randomisation( int mySwitchPinArray[], int n )
{
randomSeed(analogRead(A0));
for (int i = n-1; i > 0; i--)
{
long randNumb = random(0, n);
swap(&mySwitchPinArray[i], &mySwitchPinArray[randNumb]);
}
}
It doesn't work of course. The original code had a for loop that printed all the shuffled numbers and it worked perfectly, but when I did my thing the printed numbers repeat. Probably my nonexistent understanding of pointers contributed to the code not working correctly, so I beg you to help me fix it.
It looks like you expect 'i' to start at some value and, after you increment it, to have the incremented value the next time loop() is called. To do that, use "static int i = 0;". The 'static' lets it retain value between calls (like a global variable). The "= 0" isn't strictly necessary but it makes your intention clearer,
void loop() {
int i;
b.update();
randomisation(mySwitchPinArray, n);
if(b.rose() && i < n){ // wrong stuff here
i++;
Serial.print(mySwitchPinArray[i]);
Serial.print(" ");
}
}
hzrnbgy:
Here's an algorithm that will generate 10 random numbers of values from 0 to 9, without repeating one of them
this is pretty inefficient as it gets increasingly complicated to find something you did not use yet and the further you go in the array the more difficult it is.
If you try your algorithm with a much larger array (say 100 entries) you'll see your code will become super slow or might even not terminate in a reasonable time.
The easiest way to do this is to create an array with {0,1,2,3,4,5,6,7,8,9} and to exchange two entries selected randomly multiple times.
if you perform 5 to 10 exchanges (half the size to the size of the array) you'll get already some good entropy.
My solution is the one I came up with after reading the post.
Your solution is probably the product of a Computer Science doctoral dissertation. I'm pretty sure there are other more efficient/faster code than what I came up with, but that is a secondary concern at the moment
Your solution is probably the product of a Computer Science doctoral dissertation
not really, just a simple approach to avoiding duplicates. it also has the advantage of shuffling whatever array you have, the content does not matter.
I'm pretty sure there are other more efficient/faster code than what I came up with
out of curiosity try your algorithm with your data array holding 100 values instead of 10.
One way to pick numbers from an array in random order without repeats:
int array[] = {1, 2, 3, 4, 5};
const int arraySize = sizeof array / sizeof array[0];
int remainingNumbers = 0;
int getRandomEntry()
{
if (remainingNumbers == 0)
remainingNumbers = arraySize; // Start over with a full array
// Pick a number from those remaining
int index = random(remainingNumbers); // 0 to remainingNumbers - 1
int returnValue = array[index];
// Swap the chosen number with the number at the end of the current array
// (unless the chosen entry is already at the end)
if (index < remainingNumbers - 1)
{
// Move the last entry into the chosen index
array[index] = array[remainingNumbers - 1];
// Move the value from the chosen index into the last entry
array[remainingNumbers - 1] = returnValue;
}
// Shorten the list so the picked number is not picked again
remainingNumbers--;
return returnValue;
}
// Sketch for testing
void setup()
{
Serial.begin(115200);
}
void loop()
{
for (int i = 0; i < arraySize; i++)
{
Serial.print(getRandomEntry());
Serial.print(' ');
}
Serial.println();
delay(1000);
}
It looks like you expect 'i' to start at some value and, after you increment it, to have the incremented value the next time loop() is called. To do that, use "static int i = 0;". The 'static' lets it retain value between calls (like a global variable). The "= 0" isn't strictly necessary but it makes your intention clearer
Wow thanks! I had no idea static exists. It does work a lot better but it (mostly) failes at the last int.
For example it prints:
3 1 2 4 1
1 5 3 4 1
2 4 5 3 1
1 2 3 5 1
The last number is always 1, no matter if it is already printed. Do you know why that is?
Also, thanks hzrnbgy for your code! I might use it in the future couz I think it's easier to understand. No pointers.
do you mean 2 in a row or that you should have printed the whole array before going back to one of the previously printed element?
Oh and, the second one.
Thank you all for the help so far. Didn't expect so many replies so soon
lj_sk:
Wow thanks! I had no idea static exists. It does work a lot better but it (mostly) failes at the last int.
post your new code... (if you keep increasing i then you'll be out of bounds as static will keep it's value over each loops. In the first code the variable was reset at every loop and since it was not initialized would take whatever value is on the stack at that time/location. static and globals are initialized with 0)
Ah yes, the new code. Here it is. And uh, sorry for the late reply heh... school and stuff...
#include <Bounce2.h>
Bounce b = Bounce();
int button = 8;
int mySwitchPinArray[] = {1, 2, 3, 4, 5};
int n = sizeof(mySwitchPinArray)/ sizeof(mySwitchPinArray[0]);
void setup() {
Serial.begin(9600);
b.attach(button,INPUT);
b.interval(25);
}
void loop() {
static int i = 0;
b.update();
randomisation(mySwitchPinArray, n);
if(b.rose() && i < n){ // wrong stuff here
i++;
Serial.print(mySwitchPinArray[i]);
Serial.print(" ");
}
}
void swap (int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void randomisation( int mySwitchPinArray[], int n )
{
randomSeed(analogRead(A0));
for (static int i = n-1; i > 0; i--)
{
long randNumb = random(0, n);
swap(&mySwitchPinArray[i], &mySwitchPinArray[randNumb]);
}
}
I changed both -i- to static because it gives me the best results. If I don't put the -i- below to static as well the last number that it would print would be something like -917127. So the printed numbers would look something like 5 3 1 2 -98136. Its actually not that big of a deal anymore since I got so many good code ideas but I am just curious about why it is doing that.
lj_sk:
Its actually not that big of a deal anymore since I got so many good code ideas but I am just curious about why it is doing that.
there are many things wrong in your code but to the specific question you raise, the issue is here
if(b.rose() && i < n){
i++; // <<====== incrementing i too early !!!
Serial.print(mySwitchPinArray[i]);
Serial.print(" ");
}
you test the variable 'i' for bounds (less than array size) which is OK but in the brackets you increment it before printing. thus when you enter the test at the end of the array you print whatever is beyond the boundaries of the array. hence the garbage you see for the last value.
=> If you move the i++ after the prints then you'll be fine
Other comments:
there is no need for a static local variable in a for loop. if you come back the for statement will initialize it again.
you shuffle your array all the time as the loop spins. that's not useful. You probably would want to shuffle it only when your button is pressed for example.
note that your code only prints 1 value when the button is pressed. As you shuffle values all the time you are not guaranteed to see the 5 digits only once in the console.
it's a bad idea to use re-use global variable names for functions parameters as it brings confusion. Don't do void randomisation( int mySwitchPinArray[], int n ) but dovoid randomisation( int anArray[], int numberOfElements)
You are using C++, if pointers are confusing to you, you can pass stuff by reference.
christop:
I'll just leave this here: Fisher–Yates shuffle. It's fast and extremely simple, so there's no need to reinvent the wheel poorly.
It requires n-1 permutations. If you are time constrained, although not as statistically unbiased, picking n/2 random swaps leads to an often good enough permutation of the array and is twice as fast.
J-M-L:
It requires n-1 permutations. If you are time constrained, although not as statistically unbiased, picking n/2 random swaps leads to an often good enough permutation of the array and is twice as fast.
It's more likely that the random function itself takes the lion's share of the computation time (with its multiplies and additions and divisions), so calling it the same number of times would make that shuffle algorithm take roughly the same amount of time as a proper Fisher-Yates shuffle. If I had to choose between two algorithms in which the only significant difference between the two is the quality of the shuffle, I'd take the algorithm that produces a better shuffle.
