Randomized order of numbers in an array

Posted By: Clemens

Randomized order of numbers in an array - 04/01/10 20:41

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

Posted By: Joey

Re: Randomized order of numbers in an array - 04/01/10 22:41

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).

Posted By: MrGuest

Re: Randomized order of numbers in an array - 04/02/10 01:26

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

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

Posted By: Clemens

Re: Randomized order of numbers in an array - 04/03/10 19:40

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

Posted By: DJBMASTER

Re: Randomized order of numbers in an array - 04/03/10 19:53

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.

Posted By: Clemens

Re: Randomized order of numbers in an array - 04/05/10 13:07

Thanks for these hints and the useful example!