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

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();

Answer 2

Use a list of integers instead:

List<int> myRands = new List<int>();
int newRand = myRandGen.Create();
if (!myRands.Contains(newRand))
    myRands.Add(newRand);
...
return myRands.ToArray();

Answer 3

Here's a naive implementation :

int[] values = new int[100];
Random random = new Random();
for(int i = 0; i < values.Length; i++)
{
    int v;
    do
    {
        v = random.Next(100) + 1;
    } while (Array.IndexOf(values, v) != -1)
    values[i] = v;
}

But it would be pretty inefficient, especially near the end of the array...

A better solution would be to consider that, since you want 100 distinct values from 1 to 100 in a random order, your array will eventually contain all possible values from 1 to 100. So you just need to generate a sequence of these values, and "shuffle" it :

int[] values = Enumerable.Range(1, 100).ToArray();
Random random = new Random();
for(int i = values.Length - 1; i > 0; i--)
{
    int j = random.Next(i + 1);
    int tmp = values[i];
    values[i] = values[j];
    values[j] = tmp;
}

---

EDIT: a better approach, which should work for less specific cases :

T[] RandomCombinationWithNoRepeat<T>(IEnumerable<T> itemsToPickFrom, int numberOfItemsToPick)
{
    // Copy original items to pick from, because we need to modify it
    List<T> itemsCopy = new List<T>(itemsToPickFrom);
    T[] array = new T[numberOfItemsToPick];
    Random random = new Random();
    for(int i = 0; i < numberOfItemsToPick; i++)
    {
        // Pick item and remove it from list
        int index = random.Next(itemsCopy.Length);
        array[i] = itemsCopy[index];
        itemsCopy.RemoveAt(index);
    }
    return array;
}

In your case, you would use it like that :

int[] result = RandomCombinationWithNoRepeat(Enumerable.Range(1, 100), 100);

Answer 4

From your description I take that you need an array of 100 integer numbers with values from 1 to 100 and no duplicate numbers. If the numbers are integers you do not need to generate random numbers, as all the possible numbers are in the array. Therefore, only the order or the numbers can be randomized.

Using Linq and Jesper Palm's approach - with Thomas Levesque's the following statement will give you the array you need.

Random rnd = new Random();
var randomNumbers = Enumerable.Range(1, 100)
                              .Select(x => new { val = x, order = rnd.Next() })
                              .OrderBy(i => i.order)
                              .Select(x => x.val)
                              .ToArray();

The method is even quite fast, definately more efficient than any comparison operations.

To explain the above to the original poster, see comment below:

• Enumerable.Range(1, 100) creates a range of integers starting at 1 and ending at 100.
• .Select(x => new { val = x, order = rnd.Next() }) creates a new temporary object holding the value and the order position, which is determined by a random number.
• .OrderBy(i => i.order) sorts the temporary objects by its order position.
• .Select(x => x.val) selects the value of the temporary object, thus converting back to int.
• .Select(x => x.val) turns the whole thing back to an array again.

The syntax used is LINQ which is available in .NET 3.5. With older versions you wold have to implement it yourself, which is a lot more complicated and quite longer.

Following Eric's comment: If shuffeling is requried you can do the code as follows

var list = myInputList;
var result = list.Select(x => new { val = x, order = rnd.Next() })
                 .OrderBy(i => i.order)
                 .Select(x => x.val)
                 .ToArray();

Answer 5

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.