Gamestudio Links
Zorro Links
Newest Posts
Trading Journey
by howardR. 04/28/24 09:55
basik85278
by basik85278. 04/28/24 08:56
Zorro Trader GPT
by TipmyPip. 04/27/24 13:50
Help with plotting multiple ZigZag
by M_D. 04/26/24 20:03
Data from CSV not parsed correctly
by jcl. 04/26/24 11:18
M1 Oversampling
by jcl. 04/26/24 11:12
Why Zorro supports up to 72 cores?
by jcl. 04/26/24 11:09
AUM Magazine
Latest Screens
The Bible Game
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Who's Online Now
0 registered members (), 730 guests, and 1 spider.
Key: Admin, Global Mod, Mod
Newest Members
wandaluciaia, Mega_Rod, EternallyCurious, howardR, 11honza11
19049 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
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 Offline OP
Senior Member
Clemens  Offline OP
Senior Member

Joined: Sep 2003
Posts: 303
Germany
I wrote a function, which fill an array with numbers in a random order:

Code:
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] #317715
04/01/10 22:41
04/01/10 22:41
Joined: Jan 2003
Posts: 4,615
Cambridge
Joey Offline
Expert
Joey  Offline
Expert

Joined: Jan 2003
Posts: 4,615
Cambridge
i think not, the "continue" continues only the for loop. use "break" instead. but otherwise the function does its job.

by the way, for large arrays shuffling is faster and works in O(length), while your algorithm takes O(length^2).

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
M
MrGuest Offline
Serious User
MrGuest  Offline
Serious User
M

Joined: Jul 2008
Posts: 1,178
England
Originally Posted By: Clemens
I wrote a function, which fill an array with numbers in a random order:

Code:
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
Code:
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 Offline OP
Senior Member
Clemens  Offline 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:
Code:
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 Offline
Serious User
DJBMASTER  Offline
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.
Re: Randomized order of numbers in an array [Re: DJBMASTER] #318128
04/05/10 13:07
04/05/10 13:07
Joined: Sep 2003
Posts: 303
Germany
Clemens Offline OP
Senior Member
Clemens  Offline OP
Senior Member

Joined: Sep 2003
Posts: 303
Germany
Thanks for these hints and the useful example!


Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1