Random number generator in C# - unique values

Question

I'm busy in C# with coding an array. I can fill it up with random generators but now is my question how do i do this but so that i can check if the value is already in the array and if so generate an new value

Extra info:
Max value : 100
Number of elements : 100

IMPORTANT PLZ WORK FURTHER ON MY IDEA

my idea

public void FillArray(int[] A, int Range)
{
    for (int I = 0; I < A.Length; I++)
    {
        A[I] = ValidNumber(T, I, Range);
    }
} /* Fill Array */

Implementation of selection sort

public void SelectionSort(int[] A)
{
    int K, X;
    for (int I = 0; I < A.Length - 1; I++)
    {
        K = I;
        X = A[K];
        for (int J = I + 1; J < A.Length; J++)
        {
            if (A[J] < X)
            {
                K = J;
                X = A[K];
            }
        }
        A[K] = A[I];
        A[I] = X;
    }
} /* Selection sort */

These are just some ideas now i want to know how i can fix it so i can look with selection sort if there is allread there (fillarray) that is same if so replace it with a new random value. And so i want to create a random array with ints - from 1 to 100 in a random order

Answer 1

how do i do this but so that i can check if the value is already in the array and if so generate an new value

You don't do that, ever, because that is a very bad idea.

To illustrate why it is a terrible idea, consider another version of the same problem: sort a million numbers into a random order by the following process:

1. Choose a number from one to a million.
2. Check to see if it is on the list already.
3. If it is, go back to step 1
4. Otherwise, add the number to the list.
5. Does the list have one million items on it? If yes, you're done. If not, go back to step 1.

Clearly this works. Is it a good idea? Let's suppose you're almost done. The list has 999999 items on it. The only missing item is 857313. What do you do? You choose a random number, say, 12. Now you check the 999999 items on the list to see if any of them are 12. 12 might have been one of the first numbers you chose, so it might be fast to find it. Or it might be one of the last, so it will take a long time. On average it will take 500000 checks to see if 12 is on the list. And it is, since there is only one number missing from the list.

12 didn't work out. Go back to the beginning. Choose another random number, say, 53259. Is that on the list? Another half-million checks.

Keep doing that until you generate 857313, which happens one every million tries.

So, on average, to put the last item in the list takes 500000 x 1000000 = five hundred billion comparisons. It might take way more. It might take several trillion comparisons. Or you might get lucky and it takes one. But on average, half a trillion comparisons.

This is a terrible way to produce a random ordering of a list.

There are two good ways to make a random ordering of a list.

(1) Make a device which can sort a list given an ordering function. Provide a stable ordering that is based on a random seed.

Note that you should not produce a random ordering by making a method that returns random results when asked "is A bigger than B?" That is an unstable ordering; many sort algorithms are predicated on a stable sort ordering and will go into infinite loops or have other bad behaviour when given an unstable sort ordering.

This algorithm is O(n lg n) and has the nice property that it is very easy to write out of standard parts, as other answers indicate. It is also extremely fast for small lists in typical implementations.

(2) Choose an item by index from a source list at random, removing it from the source list as you go, and putting it on the destination list.

The latter is known as Knuth Shuffle or Fischer-Yates Shuffle, and it is a very fast algorithm. You can do it "in place", mutating an existing array into shuffled order, or by creating a new list. It also has the nice property that you can "pay for play", shuffling the "top" of the list as you need it. If you have a million items to shuffle but you only need the first one hundred, you can just work out the sort order for the first hundred and call it good.

Answer 2

The following will generate an array with the numbers 1-100 in random order.

    Random rnd = new Random();
    var randomNumbers = Enumerable.Range(1, 100).OrderBy(i => rnd.Next()).ToArray();