Filling an array randomly with no repetitions

Question

I'm trying to fill an array with random numbers from 1-10 with no repeat. I try to do it with recursion. I'm trying to it with recursion and without (here is both with, no luck in either way). I have two codes, boths not working:

1:

static int reco(int arr,int[] times)
{
    Random rnd = new Random();
    arr = rnd.Next(1, 11);
    return times[arr] > 0 ? reco(arr, times) : arr;
}

static void Main(string[] args)
{
    int i = 0;
    int[] arr = new int[10];
    int[] times = new int[11];
    Random rnd = new Random();

    for (i = 0; i < 10; i++)
    {
        arr[i] = rnd.Next(1, 11);
        times[arr[i]]++;

        if (times[arr[i]] > 0)
            arr[i] = reco(arr[i], times);
    }

2:

static int reco(int arr,int[] times)
{
    Random rnd = new Random();
    arr = rnd.Next(1, 11);
    if (times[arr] > 0)
        return reco(arr, times);
    else
        return arr;
}
static void Main(string[] args)
{
    int i = 0;
    int[] arr = new int[10];
    int[] times = new int[11];
    Random rnd = new Random();
    for (i = 0; i < 10; i++)
    {
        arr[i] = rnd.Next(1, 11);

        if (times[arr[i]] > 0)
            arr[i] = reco(arr[i], times);

        times[arr[i]]++;
    }
}

If you mean fill an array 0..N with the values 0..N in random order, the standard way of doing that is to fill the array with the values 0..N first, then iterate over the array and exchange each value with another one at a random position in the array - i.e. a shuffle. — 500 - Internal Server Error, Feb 14 '13 at 22:19

sa_ddam213 · Answer 1 · 2013-02-14T22:46:41.480

4

If you just want random numbers between 1 and 10, you could just use Enumerable.Range and order randomly.

var ran = new Random();
int[] randomArray = Enumerable.Range(1, 10).OrderBy(x => ran.Next()).ToArray();

edited Feb 14 '13 at 22:46

answered Feb 14 '13 at 22:23

sa_ddam213

42,848
7
101
110

2

Guids are not a source of randomness; they are a source of uniqueness. The guid generator is permitted to generate sequential guids. **If you are not using a guid for uniqueness, you are doing something wrong.** – Eric Lippert Feb 14 '13 at 22:37
@EricLippert, I would find it strange for Guid.NewGuid() to spit out a whole bunch of sequential GUIDS, but I see your point, and updated my answer to use Random instead :) – sa_ddam213 Feb 14 '13 at 22:49
All that new guid guarantees you is that there is an extremely high probability that the generated guid is unique. (There are scenarios in which even version 1 guids are not unique.) Version 4 guids are pseudo-random, but there is no guarantee that the guid generator generates a version 4 guid. Many guid generators generated sequential version 1 guids back in the day. – Eric Lippert Feb 14 '13 at 23:58

score 2 · Answer 2 · edited May 23 '17 at 11:54

2

Generate unique "random" numbers within a specific range like:

List<int> theList = Enumerable.Range(0, 10).ToList();
theList.Shuffle();

Example output:

[1,5,4,8,2,9,6,3,7,0]

Shuffle function (source: Randomize a List<T>):

public static void Shuffle<T>(this IList<T> list)  
{  
    Random rng = new Random();  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

edited May 23 '17 at 11:54

Community

1
1

answered Feb 14 '13 at 22:23

Anne

26,765
9
65
71

2

So far this is the only solution which is both uniformly distributed (to the extent that Random produces a uniform distribution) and efficient for arbitrarily sized lists. – Eric Lippert Feb 14 '13 at 22:41
I'd pass in the instance of `Random`. The default constructor of `Random` is broken-by-design. – CodesInChaos Feb 17 '13 at 13:28

score 1 · Answer 3 · answered Feb 14 '13 at 22:51

Since you're using C#, and you know the random numbers in the array, why not just create an array, then randomize the positions? Here is an example:

using System.Linq;

//......

Random rand = new Random();
int[] randomNumbers = new int[10] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
randomNumbers.OrderBy(num => rand.Next());

score 0 · Answer 4 · answered Feb 14 '13 at 22:20

0

    static void Main()
    {
        int[] arr = new int[10];
        List<int> numbers = Enumerable.Range(1, 10).ToList();
        Random rnd = new Random();
        for (int i = 0; i < 10; i++)
        {
            int index = rnd.Next(0, numbers.Count - 1);
            arr[i] = numbers[index];
            numbers.RemoveAt(index);
        }
    }

answered Feb 14 '13 at 22:20

Parimal Raj

20,189
9
73
110

1

Though this solution works for small arrays, consider what would happen if you tried to use it to shuffle a million elements. How long would it take your program to run? – Eric Lippert Feb 14 '13 at 22:39
@EricLippert - agree sir! but what is the solution for huge range? – Parimal Raj Feb 14 '13 at 22:44
1

Knuth-Fischer-Yates shuffle. – Eric Lippert Feb 14 '13 at 23:55

Daniel A.A. Pelsmaeker · Answer 5 · 2013-02-14T23:01:10.217

0

You could do this. The recursive version is left as an exercise for the original poster because the question sounds like a homework exercise:

int[] arr = new int[10];

// Fill the array with values 1 to 10:
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = i + 1;
}

// Switch pairs of values for unbiased uniform random distribution:
Random rnd = new Random();
for (int i = 0; i < arr.Length - 1; i++)
{
    int j = rnd.Next(i, arr.Length);

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

This uses the Fisher-Yates (Knuth) shuffle as proposed by Eric Lippert in the comments below.

edited Feb 14 '13 at 23:01

answered Feb 14 '13 at 22:26

Daniel A.A. Pelsmaeker

47,471
20
111
157

Your number of swaps is (1) unnecessarily large, and (2) does not produce a uniform distribution. Consider using a Knuth shuffle instead. – Eric Lippert Feb 14 '13 at 22:40
@EricLippert: I never heard about this algorithm before. I understand why it works and changed the code accordingly. – Daniel A.A. Pelsmaeker Feb 14 '13 at 23:03

Filling an array randomly with no repetitions

5 Answers5

Linked