C# Number Generation Question

[WelshDdraig]

Hey everyone,

 

I've made some code to generate an array full of random numbers (between 2 points), to create a "Set" of data to be analyzed.

This works fine - I've got my random set, but for it to be counted as a valid set, it has to have no duplicate numbers.

 

Sure, I can make the RNG to a really high number and hope I don't get a duplicate, but that is beside the point.

(In fact, I tried that and still got 3 repeated numbers...)

 

How would I make my RNG generate a random set of numbers without duplicates? 

 

Here's the code for my RNG if this is of any help:

		int length = 9;
            Random r = new Random();
            int yes;

            int[] setS = new int[9];

            for (int i = 0; i < length; i++)
            {
                setS[i] = r.Next(1, 19);

                Console.WriteLine(setS[i]);
            }

I've had a look at multiple sites, such as StackOverflow and I don't fully understand the methods people are showing on how to solve this problem.

 

Thanks for any help given.

[espurritado]

The easiest way to do it would be to generate the random number to an auxiliar variable, check if the generated number is in the set and if it's not, add it to the set.

 

On the amount of numbers you are generating for that range is more than likely that at least one, if no more, are repeated if you don't check. If you want to understand this try reading about the birthday problem.

[xentropa]

In my opinion, one way to do this is.

 

Create an array of sequential numbers

 

array[1]  = 1

array[2] = 2

.

.

.

array[n] = n

 

Use a random number generator to create a random index and access a single element.

 

Once that element has been accessed and copy pasted, delete that element and resize the array.  So now the new array will look something like

 

array[1]  = 1

array[2] = 2

.

(some array in between was accessed and then deleted)

.

array[n - 1] = n

[vorticalbox]

using System.Linq;
if(!array.Contains("value"))
{
    //number is not in array so add
}

 

[WelshDdraig]

4 minutes ago, vorticalbox said:

using System.Linq;
if(!array.Contains("value"))
{
    //number is not in array so add
}

 

 

Thanks, but I forgot to add, this code is now allowed to use any OO principles, so no linQ or anything - which is stupid as to why I am not allowed to use the benefit of c#...

[WelshDdraig]

I think I have come up with something that could work:

int length = 9;
            Random r = new Random();
            int yes;

            int[] setS = new int[9];

            for (int i = 0; i < length; i++)
            {
                setS[i] = r.Next(1, 19);

                for (int j = 0; j < length; j++)
                {
                    if (setS[i] == (int)r)
                    {
                        r = new Random();                        
                    }

                    Console.WriteLine(setS[i]);
                }
            }

but I cannot use the "==" operator as I can't apply it to operands of Int and Random.

So I tried casting the Random as an int (as can be seen in the code)

if (setS[i] == (int)r)
{
   r = new Random();                        
}

but now I'm getting an error saying I can't convert type "System.Random" to "Int"

[mariushm]

A random number is random by definition, it's perfectly natural to have two identical numbers in an array by accident if those numbers were generated randomly

 

However, if you want an array of random numbers (each a random number between x and y) and then each number must also be unique in the array, then what you must do is check if the random number was already added to the array.

 

Here's how this would be done (writing it in PHP but you can adapt it to c# , i'm not using associative arrays which would make this so much easier.

 

$numbers = array();  // an array with unlimited elements, starting from 0

$numbers_max = 10;

for ($i=0;$i<$numbers_max;$i++) { // give each of the numbers_max numbers a default value of 0
	$numbers[$i] = 0;
}

$value_min = 100; 
$value_max = 999; 

$value = mt_rand($value_min,$value_max); // pick a random number between 100-999

// put this first value in the array on the first element 
// since we know the array is empty, we dont have to check 
  
$numbers[0] = $value;  

// now go from the 2nd number to the last and create random numbers and test

for ($i=1;$i<$numbers_max;$i++) { 
	// $is_valid is a variable which says true if the new number we pick
	// is not already in the array. We set this to FALSE to force the
	// while loop to go at least once, in order to generate the new number	 
	$is_valid = FALSE;
	while ($is_valid==FALSE) {
		// generate a new number
		$new_number = mt_rand($value_min,$value_max);
		// assume this number is not already in the array
		$is_valid=TRUE;
		// now actually check the previous elements in array against this one
		// and set back is_valid to FALSE if the element is found. This will restart
		// the loop and another number will be generated and tested and so on
		// until a number that's not already in array is found.
		for ($j=0;$j<$i;$j++) {
			if ($numbers[$j] == $new_number) $is_valid=FALSE;
		}
	}
	// if we're here, new_number holds our unique number so we store it in array
	$numbers[$i] = $new_number;
	// and now the for loop moves on to the next number
}
                      
                      
                      
                      
                     

In c# you probably have dictionary or stacks or other structures, which would allow you to put one number after another in the collection of elements and check more quickly if a previously stored number has the same value (instead of using a for to compare against every previously stored value)

For a bunch of numbers (10-100) this code would run fast, but the more numbers you have to choose, the slower my code would be as it has to check all previous numbers every time you add a new one.

 

[MrDrWho13]

EDIT: Changed to actually work.

 

This should work if I'm understanding the problem correctly:

int length = 9;
            Random r = new Random();
            int yes;

            int[] setS = new int[9];

            for (int i = 0; i < length; i++)
            {
                bool valid = true;
                int randomNumber;
                do
                {
                    randomNumber = r.Next(1, 19);
                    valid = true;
                    
                    for (int k = 0; k < setS.Count(); k++)
                    {
                        if (setS[i] == randomNumber)
                        {
                            valid = false;
                        }
                    }
                } while (!valid);


                setS[i] = randomNumber;

                Console.WriteLine(setS[i]);

 

Edited May 8, 2017 by MrDrWho13

[WelshDdraig]

16 minutes ago, MrDrWho13 said:

EDIT: Changed to actually work.

 

This should work if I'm understanding the problem correctly:

for (int k = 0; k < setS.Count(); k++)
                  

 

 

 

While I thank you for that, I'm not allowed to use any linQ as I have to avoid any oo practices

EDIT: and I just tried it with linQ and it would still produce duplicates.

[Mira Yurizaki]

Statistically speaking, if you have an array of 9 elements and a range of 18 values, there's a very good chance you'll have the same number come up in a given "roll", even if the random number generator is truly random (due to the Birthday Paradox)

 

Storing a history of already selected numbers has the problem that the closer the size of the data set is to the range of values, the longer this will take because you're reducing the chances of a valid number showing up. For example, if you're trying to pick out two values out of the 18, you have an 11.11...% chance of getting a value. If you had a larger range like 1000, now you have a 0.2% chance.

 

The way I would do it is define the number range itself in its own data structure, pick a random entry, then delete the values off as they're chosen. However you choose to do this is up to you, but this is not an OO method. You could use a liked list (C# has a class for it though) and it would be valid, considering that you can make this in C.

[vorticalbox]

3 hours ago, Alexp10v2 said:

I'm not allowed to use any linQ as I have to avoid any oo practices

Such a stupid requirement. OOP is literally the heart of modern programming.

[Mira Yurizaki]

3 hours ago, vorticalbox said:

Such a stupid requirement. OOP is literally the heart of modern programming.

Well what's worse, C# is a OOP heavy language.

[straight_stewie]

14 hours ago, Alexp10v2 said:

While I thank you for that, I'm not allowed to use any linQ as I have to avoid any oo practices

If you're having trouble finding a good algorithm to search a random list of integers (aren't we all), then you can also do this:
 

1. Generate an array filled with integers Min to Max
2. Generate an array of Length (the length of the array you are supposed to return)
3. Generate a random number between 0 and Max minus Min.
4. If the number in the MinMax array at RandomNumber is less than Min, go back to step 3. Otherwise, go to step 5.
5. Index into the MinMax array using the random number and insert the number found there into the array that will be returned. 
6. Set the number in the MinMax array at the random number to Min minus one. 
7. If the array to be returned is not full, go to step 3.
8. Return the array

[Mira Yurizaki]

9 hours ago, straight_stewie said:

If you're having trouble finding a good algorithm to search a random list of integers (aren't we all), then you can also do this:
 

1. Generate an array filled with integers Min to Max
2. Generate an array of Length (the length of the array you are supposed to return)
3. Generate a random number between 0 and Max minus Min.
4. If the number in the MinMax array at RandomNumber is less than Min, go back to step 3. Otherwise, go to step 5.
5. Index into the MinMax array using the random number and insert the number found there into the array that will be returned. 
6. Set the number in the MinMax array at the random number to Min minus one. 
7. If the array to be returned is not full, go to step 3.
8. Return the array

This has the problem I described earlier with history. If the array of random numbers you want to return is close in size to the range of random number values, this method will take longer than necessary because as you start removing the numbers, the chances of hitting a number you can use decreases. I'm not sure what the Big O value would be, but it's certainly going to be a lot larger than O(n).

 

I mean, I guess you can add "if number chosen == -1, go find the nearest number not -1", but that seems hokey at best.

[straight_stewie]

1 hour ago, M.Yurizaki said:

This has the problem I described earlier with history. If the array of random numbers you want to return is close in size to the range of random number values, this method will take longer than necessary because as you start removing the numbers, the chances of hitting a number you can use decreases. I'm not sure what the Big O value would be, but it's certainly going to be a lot larger than O(n).

 

I mean, I guess you can add "if number chosen == -1, go find the nearest number not -1", but that seems hokey at best.

Both methods presented run in non deterministic time and have the same problem that you mentioned. In both algorithms, you are getting a random number and then checking if you've already used it. This means that you could potentially run forever. Interestingly, there is also a special case of the general problem where no solution exists, and that is where the size of the domain [Min, Max] is smaller than the length of the array you are supposed to be returning.

[Mira Yurizaki]

8 minutes ago, straight_stewie said:

Both methods presented run in non deterministic time and have the same problem that you mentioned. In both algorithms, you are getting a random number and then checking if you've already used it. This means that you could potentially run forever. Interestingly, there is also a special case of the general problem where no solution exists, and that is where the size of the domain [Min, Max] is smaller than the length of the array you are supposed to be returning.

I'm assuming the size of the array of chosen values has equal to or less than the range of random numbers.

 

I had a solution that involved a dynamic data structure, where the entries would be removed as you chose them. It would make the algorithm O(n). That would depend if the List class is considered using "OO concepts", even though you can do the same thing in C with some elbow grease.

 

Alternatively if you need static allocated arrays, you could rebuild the array every round by putting used entries in the rear and having the random picker choose only up to the new "last" entry.

[straight_stewie]

Just now, M.Yurizaki said:

I had a solution that involved a dynamic data structure, where the entries would be removed as you chose then. It would make the algorithm would be O(n). That would depend if the List class is considered using "OO concepts", even though you can do the same thing in C with some elbow grease.

I had pondered this as well, but I came to the same solution you did. I think the best way to minimize the coefficient on n would be to use a segmented array, but you could use any other dynamic data structure.

[Mira Yurizaki]

Just now, straight_stewie said:

I had pondered this as well, but I came to the same solution you did. I think the best way to minimize the coefficient on n would be to use a segmented array, but you could use any other dynamic data structure.

I added another solution in my post if you must use static allocated arrays, but I'll repeat it for convenience:

 

4 minutes ago, M.Yurizaki said:

Alternatively if you need static allocated arrays, you could rebuild the array every round by putting used entries in the rear and having the random picker choose only up to the new "last" entry.

 

[straight_stewie]

9 minutes ago, M.Yurizaki said:

Alternatively if you need static allocated arrays, you could rebuild the array every round by putting used entries in the rear and having the random picker choose only up to the new "last" entry.

This involves alot of swaps, but it's probably the best solution so far.

P:S. I think I crossed 1000 forum posts on this reply.

[Mira Yurizaki]

50 minutes ago, straight_stewie said:

This involves alot of swaps, but it's probably the best solution so far.

P:S. I think I crossed 1000 forum posts on this reply.

I got bored and coded it in C. It seems to work pretty well. The gist of it is:

while(set_idx != ARRAY_SIZE){
  int temp;
  int index = rand() % rand_range;
  set_array[set_idx ++] = numbers[index];
  temp = numbers[index];
  numbers[index] = numbers[rand_range];
  numbers[rand_range] = temp;
  rand_range --;
}

I believe this is still O(n).

 

EDIT:  Just as an aside, I could use a XOR swap, but I'm not doing that anymore. Wikipedia (yay) had some reasons behind it:

Quote

In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient. Limited situations in which XOR swapping may be practical include:

• on a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes
• in a region with high register pressure, it may allow the register allocator to avoid spilling a register
• in microcontrollers where available RAM is very limited.

Because these situations are rare, most optimizing compilers do not generate XOR swap code

 

[_dirtyBit]

First ever post on LTT ayy. Anyways,

 

If I understood correctly, you need something like this

 

using System.Collections.Generic;

HashSet<int> GenSet(int size, int min, int max)
{
    Random random = new Random();
    HashSet<int> set = new HashSet<int>();
    while (set.Count < size)
    {
        set.Add(random.Next(min, max));
    }
    return set;
}
      
// Usage example:
HashSet<int> set = GenSet(9, 0, 20); // Creates set of 9 integers from 0 to 20

 

Apologies if this isn't what you were looking for or if something is wrong, only been coding C# for less than a week.