0 registered members (),
730
guests, and 1
spider. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Randomized order of numbers in an array
#317690
04/01/10 20:41
04/01/10 20:41
|
Joined: Sep 2003
Posts: 303 Germany
Clemens
OP
Senior Member
|
OP
Senior Member
Joined: Sep 2003
Posts: 303
Germany
|
I wrote a function, which fill an array with numbers in a random order:
function array_randomized_order(var* array, length, start) {
random_seed(0);
i=0;
while (i<length) {
array[i] = integer(random(length))+start;
// check if double?
for (j=0; j<i; j++) {
if (array[i] == array[j]) { // if it is:
i--; // jump back..
continue; // ..and repeat
}
}
i++;
}
}
var order[3];
array_randomized_order(order, 3, 1);
// result is either 1,2,3 or 1,3,2 or 2,1,3 or 2,3,1 or 3,1,2 or 3,2,1
This function works. My only question is, does it really works? Can you find any systematic errors? Is it surely absolute random, every time I use it? -> toward unlimited calls every order combination would have been appeared the same times?!? Any suggestions or critics? Thanks for statements, Clemens
Last edited by Clemens; 04/01/10 20:45.
|
|
|
Re: Randomized order of numbers in an array
[Re: Clemens]
#317732
04/02/10 01:26
04/02/10 01:26
|
Joined: Jul 2008
Posts: 1,178 England
MrGuest
Serious User
|
Serious User
Joined: Jul 2008
Posts: 1,178
England
|
I wrote a function, which fill an array with numbers in a random order:
function array_randomized_order(var* array, length, start) {
random_seed(0);
i=0;
while (i<length) {
array[i] = integer(random(length))+start;
// check if double?
for (j=0; j<i; j++) {
if (array[i] == array[j]) { // if it is:
i--; // jump back..
continue; // ..and repeat
}
}
i++;
}
}
var order[3];
array_randomized_order(order, 3, 1);
// result is either 1,2,3 or 1,3,2 or 2,1,3 or 2,3,1 or 3,1,2 or 3,2,1
This function works. My only question is, does it really works? Can you find any systematic errors? Is it surely absolute random, every time I use it? -> toward unlimited calls every order combination would have been appeared the same times?!? Any suggestions or critics? Thanks for statements, Clemens The way you're doing it there is greater than O^2, if you have a number being repeatedly chosen, you'll be causing problems later on when randomising larger length arrays. Here's a snippet I wrote a while ago, I've added comments so hopefully you'll see what's happening
void random_order(int* array, int max, int start){
random_seed(0);
int i, j, pos, temp[255]; //change 4 if max greater
//set up possible numbers
for(i = 0; i < max; i++){
if(i < max){
temp[i] = i + start;
}else{
break;
}
}
//set array with numbers
for(i = max; i > 0; i--){
pos = integer(random[i]); //choose number from 0 to max
array[i-1] = temp[pos]; //set in array
//remove number from possibles
for(j = pos; j < i; j++){
temp[j] = temp[j+1];
}
}
}
hope this helps
|
|
|
Re: Randomized order of numbers in an array
[Re: MrGuest]
#317950
04/03/10 19:40
04/03/10 19:40
|
Joined: Sep 2003
Posts: 303 Germany
Clemens
OP
Senior Member
|
OP
Senior Member
Joined: Sep 2003
Posts: 303
Germany
|
At first: Thank you guys! Really good and helpful input! @Joey: Of course, you are right, has to be break for less loops! Did you mean with "arrays shuffling" the way like MrGuest did it?? @MrGuest: Great code snippet!! Thanks for sharing it! However I'm wondering about your if(i < max){ [...] }else{break;} - cause that does the loop. And furthermore it has to be random(i). @both: Your calculation of the ressources the algorithms need sounds really interessting. You wrote "O(length)" or "(O^2)"- what exactly does that mean? Do you have some explanations or links about methods to see/read such programming information? I made tests with both algorithms:
testarray1[4];
testarray2[4];
for (i=1; i<=2100; i++) {
array_randomized_order(testarray1, 4, 1);
random_order(testarray2, 4, 1);
Sum1 += testarray[0]; // could have check it as well with 1/2/3
Sum2 += testarray[0];
wait(-0.2);
Sum_counter += 1;
}
The results were: 1. test: Sum1 = 5336 Sum2 = 5172 Sum_counter = 2100 2. test Sum1 = 5244 Sum2 = 5244 Sum_counter = 2100 3. test Sum1 = 5223 Sum2 = 5313 Sum_counter = 2100 2100*2.5 = 5250 => that's the ideal outcome I didn't make a significance test - but looks like both algorithm have (same) absolute acceptable results! At all I will use MrGuest's one, which is more flexible and probably faster. Greetings, Clemens
|
|
|
Re: Randomized order of numbers in an array
[Re: Clemens]
#317953
04/03/10 19:53
04/03/10 19:53
|
Joined: Nov 2007
Posts: 1,143 United Kingdom
DJBMASTER
Serious User
|
Serious User
Joined: Nov 2007
Posts: 1,143
United Kingdom
|
The O(n) or O(n^2) is called 'Big-O notation'. It is used in the field known as 'Computational Complexity Theory', specifically when analysing the complexity of algorithms.
It basically tells you how 'efficient' the algorithm is, in the best, worst and average case.
Eg, the bubble sort algorithm has a complexity of O(n^2), therefore to sort 100 numbers it will take 100^2 (10000) iterations to complete, so bubblesort isn't a particularly useful sorting algorithm.
Do some googling for 'complexity analysis' or similar and you'll find lots of information.
Last edited by DJBMASTER; 04/03/10 19:58.
|
|
|
|