----------------------------------- EnzoFox77 Sat Mar 03, 2012 3:47 pm 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? ----------------------------------- ihsh Sat Mar 03, 2012 4:13 pm RE:Help With randint ----------------------------------- You can look at this thread for the simple method: http://compsci.ca/v3/viewtopic.php?t=30725 ----------------------------------- d2isthebest Sat Mar 03, 2012 5:13 pm 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. ----------------------------------- Velocity Sun Mar 04, 2012 2:02 am 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 ----------------------------------- Tony Sun Mar 04, 2012 2:52 am RE:Help With randint ----------------------------------- ... array containing 20 integers ... What now Velocity? ----------------------------------- d2isthebest Sun Mar 04, 2012 11:09 am Re: Help With randint ----------------------------------- 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 Sun Mar 04, 2012 12:19 pm 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: % 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 Sun Mar 04, 2012 2:33 pm 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. ----------------------------------- Tony Mon Mar 05, 2012 2:44 am Re: Help With randint ----------------------------------- 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 Mon Mar 05, 2012 7:10 pm RE:Help With randint ----------------------------------- 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 Mon Mar 05, 2012 7:53 pm RE:Help With randint ----------------------------------- http://compsci.ca/v3/viewtopic.php?t=2184 ----------------------------------- Dreadnought Tue Mar 06, 2012 1:25 am Re: Help With randint ----------------------------------- 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 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 [url=http://en.wikipedia.org/wiki/Fisher-Yates_shuffle]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 Tue Mar 06, 2012 1:55 am RE:Help With randint ----------------------------------- I think you just fixed d2isthebest's code to do what the other code does :lol: 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 Tue Mar 06, 2012 1:33 pm 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.