random for loop

[stubman]

Hello everyone,

When running a regulair for loop, the variable will increase by typically one, that would give

1
2
3
4
5
etc

I am looking for a method of doing the same thing, but in random order.
like:
4
2
5
1
3
etc

I made a rather complex solution to this problem, my solution can be viewed here: C pastebin - collaborative debugging tool

Im very sure that there is a smarter and less cpu-demanding way to do this.

[laserlight]

It sounds like you want to create an array of these numbers, and then shuffle the array.

[stubman]

It sounds like you want to create an array of these numbers, and then shuffle the array.

i found this, which hopefully can aid me Ben Pfaff: How can I shuffle the contents of an array?

[MK27]

I've used an algorithm called the "Fischer-Yates" shuffle alot for randomizing arrays. It (or my version) works like this:

- loop backward through the array, from the last element to the 3rd element, ie:

int i, len = /* array length */
for (i=len; i>1; i--)

- at each iteration, generate a random number (x) from 0 to the number of the current element (i):

x = rand()%i;

- if x == i, continue, otherwise, swap element i with element x.

That's about a half dozen lines. Remember: If you don't want the results to always be the same when you run the program, use srand(time(NULL)) once in main() before the shuffle is first executed.

There's a slight imbalance in the algorithm in that elements at the end of the array have a greater chance of not being moved than elements at the beginning. If you wanted to resolve that, you could make x = rand()%len (but this actually decreases the overall randomness by creating the chance that previously shuffled elements could be swapped back) or run once forward and once backward. In practice, neither of those is necessary. Try it a few times -- the result is always a pretty thorough looking shuffle.

[stubman]

Thank you very much for sharing that :-) ill try it out!

[laserlight]

loop backward through the array, from the last element to the 3rd element

I think that to be more correct, you should actually loop to the 2nd element, i.e., when you reach the 2nd element, you are basically deciding whether or not to swap it with the first.

There's a slight imbalance in the algorithm in that elements at the end of the array have a greater chance of not being moved than elements at the beginning.

I do not think so. Consider a four element array. The probability that the element at index 3 will be moved is the probability that it will be swapped with another element, i.e., the probability that index 3 will not be generated, which is 1 - 1/4 = 3/4.

Now, the probability that the element at index 2 will be moved is the probability that it will be swapped with the element at index 3 (i.e., 1/4), and if it is not swapped with the element at index 3, then the probability that it will be swapped with an element before it in the array, i.e., 2/3. But this 2/3 is conditional on the element at index 3 not being swapped with this element, hence the probability is actually 1/4 + (3/4 * 2/3) = 3/4.

If we examine the case for the element at index 1, we see that the probability that it will be moved is:
1/4 + (3/4 * (1/3 + (2/3 * 1/2))) = 3/4
(Assuming that you loop to the 2nd element.)

(But I did not score very well for my probability module in university, so feel free to correct me if I am wrong )

EDIT:
Well, an empirical test shows that my analysis should be correct. Anyway, I noticed that although you wrote "3rd element", your code snippet has "i>1", so you are actually doing it right. One remaining problem would be that you talk about comparing if x == i, but you have to decrement i first for that to be useful.