Help With randint

[EnzoFox77]

I have an array containing 10 integers. I wish to assign each of them a random integer. The problem is that once a number is chosen, I wish to take that out of the possibilities, so that none of the 10 integers in the array are equal to each other. Any Ideas?

[ihsh]

You can look at this thread for the simple method: http://compsci.ca/v3/viewtopic.php?t=30725

[d2isthebest]

An easier way would be to assign the numbers in the array non-randomly (id element 1 = 1, element 2 = 2, element 3 = 3...) and the to shuffle your array. By shuffle i mean for each element in the array, pick another element at random and swap their values.

[Velocity]

if array num1 or num2 ... Equals array num1 or num2 then repick... Do your randint again. Thats a looong line but it will work

[Tony]

... array containing 20 integers ...

What now Velocity?

[d2isthebest]

Turing:

var nums : array 1..100 of int for a : 1..100     nums (a) := a end for var id, temp : int for  a : 1..100     id := Rand.Int (1, 100)     temp := nums (id)     nums (id) := nums (a)     nums (a) := temp end for

[Aange10]

But if there was a case where it would be counter productive to shuffle your array, I'd try a method like this:

Turing:

% Declare the array var myArray : array 0 .. 100 of int % Declare a hold our random number variable var holder : int % Declare a variable to hold our place in our element var elementPlace : int := lower (myArray) loop     exit when elementPlace = upper (myArray) + 1     /* This creates a random number between the range of the array. *      * This could be altered with no reprucussions.                 */     holder := Rand.Int (lower (myArray), upper (myArray))     % Go through our elements and see if any of them have the same number     if elementPlace not= lower (myArray) then % The first element can be anything         for i : lower (myArray) .. elementPlace - 1             % If the number is already taken             if myArray (i) = holder then                 % Exit to get a new number                 exit                 % If we are on the last element, and every element was free             elsif i = elementPlace - 1 then                 myArray (elementPlace) := holder                 elementPlace += 1             end if         end for     else         myArray (elementPlace) := holder         elementPlace += 1     end if end loop

[Dreadnought]

Aange10's method is relatively simple to understand but should be avoided when trying to construct large arrays as it scales exponentially, with a worst case scenario of infinite run time.

The shuffle method, described by d2isthebest, is much better as it runs in linear time which is the best you can hope for in this case. (for an array of 1000 elements its ~300-400 times faster than Aange10's code)

It should be noted that if you really want to use Aange10's method you can improve run time by creating an array to check if values have already been used, thus dropping the time required to check if a value is allowed from linear time to constant time at the cost of using memory. (note that overall we still have exponential run time but for 1000 elements its only ~3-4 times slower than the shuffle method)

Of course, if you are creating small arrays and run time is not an issue then this is not important.

[Tony]

Dreadnought @ Sun Mar 04, 2012 2:33 pm wrote:

The shuffle method, described by d2isthebest, is much better as it runs in linear time ...

it feels like it might not be giving an even distribution though... A better approach is to keep an array of "elements not yet selected", and randomly pick stuff out of there. O(n) runtime, O(n) space, and it uses only 2 assignment operations in the loop, instead of shuffle's 3.

[Aange10]

Quote:

A better approach is to keep an array of "elements not yet selected", and randomly pick stuff out of there. O(n) runtime, O(n) space, and it uses only 2 assignment operations in the loop, instead of shuffle's 3.

Do you think you could provide a pseudo example?

[Tony]

http://compsci.ca/v3/viewtopic.php?t=2184

[Dreadnought]

Tony wrote:

it feels like it might not be giving an even distribution though... A better approach is to keep an array of "elements not yet selected", and randomly pick stuff out of there. O(n) runtime, O(n) space, and it uses only 2 assignment operations in the loop, instead of shuffle's 3.

I checked the code at http://compsci.ca/v3/viewtopic.php?t=2184 it produces the same distribution as the method described by d2isthebest (which I shall call the "Shuffle method"). Note that D2isthebest's code doesn't actually work properly, he needs to change the lower bound of the Rand.Int to a, however the idea is correct.

Turing:

var size : int := 10 var randN : int %just to hold the number var NotShuffle, Shuffle : array 1 .. size of int for i : 1 .. size     NotShuffle (i) := i     Shuffle (i) := i end for for decreasing i : size .. 1     randN := Rand.Int (1, i)         % the "non-shuffle" code     put NotShuffle (randN), " - "..     NotShuffle (randN) := NotShuffle (i)     % Shuffle method (modified to work properly and run in decreasing order)     var temp :int := Shuffle (randN)     Shuffle (randN) := Shuffle (i)     Shuffle (i) := temp     put Shuffle (i)     /* Since the first method simply prints the number we can rewrite the Shuffle code to     put Shuffle (randN)     Shuffle (randN) := Shuffle (i)     This clearly shows that the two are equivalent and are actually doing the same thing!*/     end for

Both algorithms are in fact the same. One keeps the remaining numbers in a separate list while the other keeps them in the "not-yet-shuffled" part of itself. This algorithm is called the Fisher-Yates shuffle (or Knuth shuffle).

As for assignment, the code in your link would require a second array to store the random number sequence, thus using more memory than the Shuffle method but fewer assignment operations. Since assignment operations are relatively cheep I'd say neither method has any advantage over the other.

[Tony]

I think you just fixed d2isthebest's code to do what the other code does at this point yes, the two algorithms are the same (since you fixed it). The extra assignment issue is a typical space vs. time tradeoff... which at "10 integers" doesn't even matter.

The original attempt (one before the fix) suffers from a distribution problem as described in http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html

[Dreadnought]

Oh, sorry this was a misunderstanding on my part. I misread d2isthebest's first post and thought he meant to implement what I implemented in my last post. I just figured he forgot to change the bounds on the Rand.Int, but I now see that it was in fact what he intended. Sorry, about this, you were right all along.