Unique Number Arrays?

[Programmer_Jpk]

i was wondering how people go about getting Unique Number Array's? cause a lot of people do it very differently o_O, seen people with 100 lines of code, others with 10.. my way lately has been using HashTables

       Dim a As Integer ' Just a Counting Value
       Dim RNS As Integer = 100 ' Random Numbers i'm just using 100, cause i can
       Dim RandomValues As New Hashtable ' Hash Table, Of Course o.o
       Dim RandValue As Integer ' Random Number
       While a <> RNS
           Randomize()
           RandValue = Int((RNS - 0 + 1) * Rnd()) + 0 ' highest - Lowest + 1 ect.. 
           While RandomValues.ContainsValue(RandValue) ' If Hastable Contains The Value, Go nuts till it gets it
               RandValue = Int((RNS - 0 + 1) * Rnd()) + 0
           End While
           RandomValues(a) = RandValue if it got it, set it..
           a += 1 ' Repeat
       End While

So Yeah o.o, just wondering how people go about their random values.. and weather or not there is more simpler stuff i could steal :]

[PlausiblyDamp]

Are you looking at having the numbers 1 through 100 put into a random order or just 100 random numbers that could be larger than 100?

[Programmer_Jpk]

This code produces 100 values, checks if its already entered into the hashtable then add's it if it isn't

 

Example: Say you want 52 card values shuffled for a card game you would change the 100 to 52, and 0 to 1

 

       Dim a As Integer 
       Dim HighVal As Integer = 52 ' Highest Value Wanted
       Dim LowVal as integer = 1 ' Lowest Value Wanted

       Dim RandomValues As New Hashtable
       Dim RandValue As Integer

       While a <> HighVal 
           Randomize()
           RandValue = Int((HighVal- LowVal + 1) * Rnd()) + LowVal
           While RandomValues.ContainsValue(RandValue) 
               RandValue = Int((HighVal- 0 + 1) * Rnd()) + 0
           End While
           RandomValues(a) = RandValue
           a += 1
       End While

 

And this would add 52 Values into the Hashtable, all random

 

If you want just add a text box and

TextBox1.Text = TextBox1.Text & RandValue & ", "

after the a += 1

And you would be able to test it out for yourself

 

Which This Time Produced

"38, 34, 22, 43, 33, 24, 27, 30, 18, 4, 31, 2, 14, 28, 10, 49, 17, 8, 29, 23, 41, 20, 3, 9, 5, 0, 35, 1, 15, 25, 19, 52, 26, 47, 44, 42, 45, 46, 37, 12, 39, 32, 36, 7, 40, 48, 16, 11, 21, 51, 6, 13"

 

All i want to know is how everyone else goes about getting their own random numbers, cause most people do it differently to a degree

[MrPaul]

Pick two and swap!

 

So Yeah o.o, just wondering how people go about their random values.. and weather or not there is more simpler stuff i could steal :]

 

There certainly is a simpler way of achieving this. If your intent is to create a list containing all numbers from LowVal to HighVal, in a random order, the simplest solution is to add them all to the list sequentially, and then jumble them up by repeatedly swapping two randomly chosen items. This is easiest/fastest with an array.

 

The reason this is preferable, is that your implementation will take an indeterminate amount of time to execute. The more items that get added to the list, the more "collisions" will occur - to the point that for the last value, the loop has to keep generating random numbers until the one possible valid number is randomly chosen. For large values of HighVal, this could take forever! Compare this to the "swap items randomly" method, which will have a predictable number of swaps, and therefore a predictable time function.

 

Good luck! :cool:

Edited August 1, 2009 by MrPaul

[snarfblam]

Re: Pick two and swap!

 

Another method that guaruntees a random order would be to fill an array by picking random insertion points. Using the 52 example, start by initializing an array with 52 dummy values that indicate that that spot is empty (-1 would be typical, in this case 0 will also work).

 

You start with value 1, and pick a random number from 0 to 51 for the insertion, and place the 1 at that index. Next time, pick a random number from 0 to 50, and count through that many empty spaces (i.e. count through empty spaces, skipping used spots), then put the 2 at the nth empty spot. Then pick a random number from 0 to 49 in put the 3 in that empty spot. Using random numbers with a range equal to the number of empty spots remaining gives all empty spots an equal chance of being used each iteration.

 

Of course, if you are making a card game, you may want to use a more "legitimate" shuffling algorithm to make the game more "authentic".

[PlausiblyDamp]

Re: Pick two and swap!

 

If the data is in an array you could also use Array.Sort with a bunch of random numbers as the key

int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Random r = new Random();
byte[] b = new byte[numbers.Count()];
r.NextBytes(b);
Array.Sort(b, numbers);

although for large array numbers using a byte as a random key might not be random enough.

[Programmer_Jpk]

Re: Pick two and swap!

 

Well there sure are a few ways to make unique arrays,

 

The Swapping of items would have friction points as well? cause you would have to do it for so long, and weather or not its 'more' random would be questionable.. i do like it though, and yes mine does have problem with time, but on a everyday computer these days shouldn't be a problem unless your running like.. 10k long arrays xD o.o

 

The Byte Sort sounds pretty interesting o_O, may try both your idea's for a bit :]

[Cags]

Just to put another option into the mix (don't think it was covered, but it's late). Populate an array with the numbers in sequence. Then use Rnd() to choose a random index between 0 and the length of the array -1. Remove the value from the original array and add it to a second array. Rinse, Dry, Repeat until array 1 is empty. Voila a randomly ordered list. Probably not as efficient as some solutions suggested, but just thought I'd throw it out there.

[Programmer_Jpk]

Populated Array

 

Thats not half bad o_O

 

Might give that one a whirl one day, seems rather simple would be nice and see how efficient it is :]

[snarfblam]

Remove the value from the original array

The only problem with this is that, on average, half the source array must be re-written on each iteration. The alternative is to overwrite the used value with a dummy value, but then you must count through the array rather than indexing it, and that has it's own performance hit.

 

Of course, if your list is sanely sized the real challenge would be coming up with a technique that doesn't perform well enough.

[Cags]

Fair point, the re-writting would somewhat throw an anchor in the works. I was trying to come up with a linked list solution, but I guess that would work similar to your suggestion of blanking out the source array in as much as you'd have to count through the items.

 

As the only coding I've done in the last year is some PHP though, I'm glad I came up with a solution at all :)