Randomizing order of numbers from 1 to 10

[chopperdudes]

i'm really in need of this, i have a part of the code where i want to randomize the 10 questions i have on each difficulty level of a jeopardy game.

so for say i have an array of 1..10
how am i able to randomize the order of the numbers, 1, 2, 3,... 8, 9, 10 without repeating it? Rand.Int doesn't work because i might repeat it and therefore the same question might appear on different positions on the game board.

so all i want to know is how to randomize the order of the numbers from 1 .. 10 and put them in an array, or have an array of 1..10 and randomize that.

thx

[chopperdudes]

i know i'm not supposed to ask for answers but the best i can come up with right now is using 2 for loops to initiate and check wether the value has been assigned to any previous elements of the array.

this will take very long because each time it has to generate a Rand.Int and check, and regenerate and check...

is there any more efficient method/easy approach to this?

here's my code so far:

Turing:

var random : array 1 .. 10 of int for i : 1 .. 10     random (i) := Rand.Int (1, 10)     if i > 1 then         for k : 1 .. i - 1             loop                 if random (i) = random (k) then                     random (i) := Rand.Int (1, 10)                 else                     exit                 end if             end loop         end for     end if     put i, " ", random (i) : 5 end for

btw i dont' know why, it doesn't work. according to (my) logic it should. it repeats numbers sometimes

[Tony]

The problem is that you have random (i) := Rand.Int (1, 10) in two separate places there. Redundancy often leads to errors.

Here's a hit for a better approach, I think you might find it sufficient.

Turing:

var numbers_not_yet_selected : array 1 .. 10 of int := init(1,2,3,4,5,6,7,8,9,10)

It will be an O(n) algorithm, that is -- Rand.Int will be called just 10 times in total.

[chopperdudes]

i'm not familiar at all with O(n) algorithms, can you please explain?

and i have 2 random (i) := Rand.Int (1, 10) is because the first is to assign it, the second is to check/re-assign it until it isn't the same as any previous numbers, i don't see how that can create a problem. if the after the first Rand.Int (1, 10) and it isn't the same as any previous numbers, it skips over the 2nd Rand.Int(1, 10)

[Tony]

chopperdudes @ Fri Jun 06, 2008 9:33 pm wrote:

the second is to check/re-assign it until it isn't the same as any previous numbers

No. It only checks/re-assigns the _current_ index.

By Big-O (n) I mean what I've said already. You need only 10 Rand.Int calls to generate a random list of 10 integers.

[chopperdudes]

the thing i do not understand is how calling Rand.Int 10 times will prevent you from generating the same number. can you please explain how i would go about doin this O (n)?

thx alot

[chopperdudes]

hmm... after thinking about it, i came up with the following

Turing:

var randNum : int var random : array 1 .. 10 of int := init (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) for i : 1 .. 4     randNum := Rand.Int (i, 10)     random (i) := random (randNum)     random (randNum) := i end for for i : 1 .. 10     put random (i) end for

it basically picks an element i, assign it to a Rand.Int (1, 10), then assign element (Rand.Int) to value i. basically swapping places.

i've tested it over 10 times and it worked. but just to make sure can you see any flaw in this method?

[richcash]

It is skewed randomness (in that each element of the array has a higher probability of retaining its original value than in correctly randomized lists). It also does repeat sometimes. But you're on the right track. Only some slight adjustments are needed to get that working for any list (not just lists with values from 1 to 10).

Let's look at getting the first 2 positions in an array randomized (from all the values in the entire array).

1. We're randomizing element 1 and no values have been used up yet, since it's the beginning. Randomize from 1 to the length of the array, access the value at that index in the array, and assign it to that first position.
2. But wait, if you assign it you lose the value that was originally in the first position. The solution is to obviously swap the randomized value with the first value in the array. You can swap using a temporary variable.
3. Now we're randomizing element 2 and we DO NOT want to reuse the value we already have used (which is currently in the first position). So we just randomize from 2 to the length of the array and follow the same steps we did for the first one.

See the pattern? Do those steps for all positions in the array and you have a randomized list, done in-place.

[Tony]

So your approach swaps the first four numbers with random locations in the list... This certainly makes for _a_ result, but I'll let you figure out for yourself why this is not a result of very good quality (think about generating a lot of lists and possible trends that might come up).

chopperdudes @ Fri Jun 06, 2008 9:49 pm wrote:

how calling Rand.Int 10 times will prevent you from generating the same number.

The original hint I gave you was:

Turing:

var numbers_not_yet_selected : array 1 .. 10 of int := init(1,2,3,4,5,6,7,8,9,10)

So if you select a random number from a list of numbers that have not yet appeared in the list, you are guaranteed to not have the numbers repeat. There are 10 numbers to choose, so there are 10 Rand.Int()s to call. After generating a number to be placed into the list, all you have to do is maintain the list of numbers remaining.

Try it yourself first, then compare to the previously posted solution

[chopperdudes]

sorry to say, but your posted method does not work. instead of putting

Turing:

put numbers (randN)

inside your for loop
try to comment out that line and print out all the elements of the array numbers at the end. the following code will not work:

Turing:

var size : int := 10 var randN : int %just to hold the number var numbers : array 1 .. size of int for i : 1 .. size        numbers (i) := i end for for decreasing i : size .. 1        randN := Rand.Int (1, i)        %put numbers(randN)        numbers (randN) := numbers (i) end for for i : 1 .. size       put numbers (i) end for

[richcash]

It looks like Tony forgot to swap the values. If you swap numbers (i) and numbers (randN) in that for loop it will work.

Did you read my and/or Tony's explanation of doing this in the above posts? I think you should write an implementation of the general algorithm on your own, to test if you know it or not.


EDIT - Yep, I just tried it, switch the values and it will work. Tony did half the swap only. (Remember to use a temporary variable (or addition) when switching values.)

And re:

Tony wrote:

So your approach swaps the first four numbers with random locations in the list... This certainly makes for _a_ result, but I'll let you figure out for yourself why this is not a result of very good quality (think about generating a lot of lists and possible trends that might come up).

Actually, chopperdudes did not swap values. He made the position where he got the random value from equal to 'i' (the current element's position, but not necessarily its value). By logic, if the random value generated for one of the first 3 iterations of his for loop is in the range (i+1, 4) then I think the list will have repeating values. chopperdudes, have you still not seen your method repeat values? I tested it and it only worked sometimes.

[Tony]

richcash @ Sat Jun 07, 2008 1:06 am wrote:

EDIT - ... Tony did half the swap only.

Because that's all you need

The code, as posted, worked since 2003.

There is no need to swap any value into number(i) because on the next iteration of the loop the range becomes 1 .. (i - 1).

[richcash]

I thought the intention of your code was to randomize the array onto itself (and so did chopperdudes judging by his test). Then, obviously you would need to swap to avoid repeating values and losing the previous value at numbers(randN).

I guess your intention was to only output the random list and the user of your code would introduce their own second array if they wanted it stored. They would replace the put statement with

Turing:

second_array(i) := numbers(randN)

Then, obviously, you wouldn't need to swap since any elements after numbers(i) have no chance of being used again.

Well, your method would be a bit faster than the algorithm I posted earlier but mine uses only one array. So I guess it's up to chopperdudes to pick which one would better suit his program. Memory vs. speed.

[Reality Check]

Tony has given you all you need (and more) to solve your problem. Think about it...

[richcash]

I also gave a valid solution. The OP misinterpreted what Tony's code was supposed to do (as I did initially, I didn't know he only wanted to output it). If you don't want to store the randomly ordered list use Tony's. Otherwise Tony's will need an extra array, which is O(n) more memory, or it will have to swap to randomize the list onto itself (i.e. my solution) which is O(1) memory.