Computer Science Canada

Help With randint
Author:  EnzoFox77 [ Sat Mar 03, 2012 3:47 pm ]
Post subject:  Help With randint
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?
Author:  ihsh [ Sat Mar 03, 2012 4:13 pm ]
Post subject:  RE:Help With randint
You can look at this thread for the simple method: http://compsci.ca/v3/viewtopic.php?t=30725
Author:  d2isthebest [ Sat Mar 03, 2012 5:13 pm ]
Post subject:  RE:Help With randint
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.
Author:  Velocity [ Sun Mar 04, 2012 2:02 am ]
Post subject:  RE:Help With randint
if array num1 or num2 ... Equals array num1 or num2 then repick... Do your randint again. Thats a looong line but it will work
Author:  Tony [ Sun Mar 04, 2012 2:52 am ]
Post subject:  RE:Help With randint
... array containing 20 integers ...

What now Velocity?
Author:  d2isthebest [ Sun Mar 04, 2012 11:09 am ]
Post subject:  Re: Help With randint
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
Author:  Aange10 [ Sun Mar 04, 2012 12:19 pm ]
Post subject:  RE:Help With randint
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
Author:  Dreadnought [ Sun Mar 04, 2012 2:33 pm ]
Post subject:  Re: Help With randint
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.
Author:  Tony [ Mon Mar 05, 2012 2:44 am ]
Post subject:  Re: Help With randint
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.
Author:  Aange10 [ Mon Mar 05, 2012 7:10 pm ]
Post subject:  RE:Help With randint
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?
Author:  Tony [ Mon Mar 05, 2012 7:53 pm ]
Post subject:  RE:Help With randint
http://compsci.ca/v3/viewtopic.php?t=2184
Author:  Dreadnought [ Tue Mar 06, 2012 1:25 am ]
Post subject:  Re: Help With randint
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.
Author:  Tony [ Tue Mar 06, 2012 1:55 am ]
Post subject:  RE:Help With randint
I think you just fixed d2isthebest's code to do what the other code does Laughing 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
Author:  Dreadnought [ Tue Mar 06, 2012 1:33 pm ]
Post subject:  Re: Help With randint
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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy