I have twelve numbers in an array. I want to extract them in a random order, but so that each number is used once before any number can be used again - ie, as if someone was picking numbered balls out of a bag, then putting them all back in again before starting again.
Can anyone give me any clues because I'm struggling with where to even start!
You could just shuffle the array and pick them in order. Iterate through the array and swap the item with random value in the array. Something like
enum {num_values=12};
uint8_t arr[num_values]={/*put your numbers here*/};
for(unsigned i=0; i<num_values; ++i)
{
uint8_t idx=rand()%num_values;
uint8_t tmp=arr[i];
arr[i]=arr[idx];
arr[idx]=tmp;
}
You can try storing the index of the value pulled in some form (in my example I use the bit positions of an integer) and only allow a value to be selected if that stored indication is '0'; once pulled, that indication is set to '1' and that number is unavailable anymore. When all numbers have been chosen, the code resets the "chosen" variable and starts over again.
const byte
arr[12] = { 1,2,3,4,5,6,7,8,9,10,11,12 };
int
chosen;
void setup()
{
Serial.begin(9600);
randomSeed( analogRead(0) );
chosen = 0;
}//setup
void loop()
{
byte
idx;
bool
done = false;
while( !done )
{
do
{
idx = random( 0, 12 );
}while( (chosen & (1<<idx)) != 0 );
chosen |= (1<<idx);
Serial.print( "Chose element #" );
Serial.print( idx );
Serial.print( " (" );
Serial.print( arr[idx] );
Serial.print( ") " );
Serial.println( chosen, HEX );
if( chosen == 0xFFF )
done = true;
}//while
Serial.println( "All elements chosen. Resetting..." );
chosen = 0;
randomSeed( analogRead(0) );
delay( 500 );
}//loop
similar to above:
have a second "flag" array with equal length, boolean. Initialize "true".
Each time an index on main array is used, "false" the same index on "flag" array. Reset to "true" when all ia used.
Array of length N.
Methods above that need to look for unused elements won’t scale very well. 12 elements is one thing but looking for the last unused ones in the case of, say, 5000 elements will get kinda slow.
Backfin will be randomly shooting for an increasingly rare target, could go on for some time.
a7
Shuffle the array : use a for loop up to 3 or 4 times the number of elements, and swap two randomly chosen elements
byte arr[12] = { 1,2,3,4,5,6,7,8,9,10,11,12 };
for (byte i = 0; i<4*12; i++) {
byte index1 = random(12);
byte index2 = random(12);
byte tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
johnwasser:
Array of length N.
- Pick a random index from 0 to N-1 (index = random(N)
- Use the value at that index.
- Swap the value at that index with the value at index N-1.
- Reduce N by 1.
- Repeat until N == 0.
int Numbers[12];
void loop()
{
static byte count = 12;
if (count != 0)
{
int index = random(count);
int temp = Numbers[index];
process(temp);
Numbers[index] = Numbers[count - 1];
Numbers[count - 1] = temp;
count--;
}
else
{
// To pick the 12 numbers in a new order, set 'count' to 12
}
}
Thank you. A mixture of answers that I understand and some that I don't...not sure how you "swap" values in an array other than put one value in a temporary variable, then move the other one and finally put the temp value back. Is there an easier way?
In principle I like the "n-1" array size idea...makes sense to my Luddite brain because it reminds me that in my original example the bag will eventually run out of balls.
put one value in a temporary variable, then move the other one and finally put the temp value back.
That is how you do it.
johnwasser:
Array of length N.
- Pick a random index from 0 to N-1 (index = random(N)
- Use the value at that index.
- Swap the value at that index with the value at index N-1.
- Reduce N by 1.
- Repeat until N == 0.
I see you already posted some code while I was working on it, but this is my version
const byte array_size = 12;
byte numbers[array_size];
byte N;
byte rnd;
void setup() {
Serial.begin(9600);
}
void loop() {
N = array_size;
//load numbers 0 to N-1 into corresponding array elements
for (byte i = 0; i < N; i++) {
numbers[i] = i;
}
do {
rnd = (byte)random(N);
if (numbers[rnd] < 10) {
Serial.print(" ");
}
Serial.print(numbers[rnd]);
Serial.print(" ");
//remove the number just used by replacing it with last element of array
numbers[rnd] = numbers[N - 1];
//remove the last element of array and reduce number of elements
N--;
} while (N > 0);
Serial.println("");
}
If you want some other information in your array, instead of sequential numbers, just use the valve from the array as the index into your own array.
GreyArea:
Thank you. A mixture of answers that I understand and some that I don't...not sure how you "swap" values in an array other than put one value in a temporary variable, then move the other one and finally put the temp value back. Is there an easier way?
Yes, swapping is exactly what you described. In my own code I have swap() function which makes this kind of code slightly cleaner, but that's what it does.
What johnwasser described is a good alternative to pre-shuffling the array. Swapping an element in an array with the last element is a common technique for constant time element removal from the array, if the order doesn't matter, like in your case.
something really easy :
instead of removing an element and sorting or swaping and ..., why not replace the used with a fresh one?
.not sure how you "swap" values in an array other than put one value in a temporary variable, then move the other one and finally put the temp value back. Is there an easier way?
Try this
x = x ^ y;
y = y ^ x;
x = x ^ y;