Given N, generate sequence of random numbers from 0 to N - 1 with no repetitions

Problem statement:
Given an integer n, write a function to return an array of size n, containing each of the numbers from 0 to n-1 in a random order. The numbers may not repeat and each number must show up exactly once.

Solution # 1:
Generate an ordered array then shuffle it

private static int[] Shuffle(int n)
{
    var a = Enumerable.Range(0, n).ToArray();
    var random = new Random();
    for (int i = 0; i < a.Length; i++) {
        var j = random.Next(0, i);
        Swap(a, i, j);
    }
    return a;
}

private static void Swap(int[] a, int i, int j)
{
    var temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Solution # 2:
Generate empty array and add items in random order

private static int[] Shuffle(int n) {
    var a = new int[n];
    var random = new Random();
    for (int i = 0; i < a.Length; i++) {
        var j = random.Next(0, i);
        Swap(a, i, j);
    }
    return a;
}

private static void Swap(int[] a, int i, int j) {
    var temp = i;
    a[i] = a[j];
    a[j] = temp;
}

I'm not fully persuaded about the randomness of solution # 2. Are there better ways of achieving the solution? I'm assuming that whatever approach is taken the solution can only be produced in linear time. Is this conclusion correct?

You can use the inside out version of the Fisher-Yates shuffle

In C# it would look like:

private static int[] Shuffle(int n) 
{
    var random = new Random();
    var result = new int[n];
    for (var i = 0; i < n; i ++)
    {
        var j = random.Next(0, i + 1);
        if (i != j) 
        {
            result[i] = result[j];
        }
        result[j] = i;
    }
    return result;
}

It's good because you create and shuffle your array at the same time using a well known shuffle.

You'd want to reuse the same Random instance though.

StackExchange Code Review Q#84187, answer score: 11