6
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ More glaring is that solution 2 will always return the same array. \$\endgroup\$ – ratchet freak Mar 16 '15 at 9:50
  • \$\begingroup\$ @ratchetfreak...mmm...that's not what I observed when running it... \$\endgroup\$ – chosenbreed37 Mar 16 '15 at 9:52
  • 1
    \$\begingroup\$ Geh, method nameing tripped me up, I missed the temp=i in swap which makes it "not a swap". \$\endgroup\$ – ratchet freak Mar 16 '15 at 10:20
  • \$\begingroup\$ Name is not as good. I was just tweaking solution # 1 so I kept the method names. \$\endgroup\$ – chosenbreed37 Mar 16 '15 at 11:09
  • 1
    \$\begingroup\$ possible duplicate of Generate random numbers without repetitions \$\endgroup\$ – Dan Lyons Mar 16 '15 at 17:23
10
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Here is the most terse way to do this.

To break this down, Enumerable.Range creates an ordered array. Then, OrderBy uses a random key generated by the random number generator. This key is associated with each cell in the int[]. This means that the OrderBy will reshuffle the array based on this random key and voila: a random array of n numbers.

public static int[] Shuffle(int n)
    {
        var randomGenerator = new Random();
        return Enumerable.Range(0, n).OrderBy(x => randomGenerator.Next()).ToArray();
    }
\$\endgroup\$
3
\$\begingroup\$

naming in solution 2 is rather bad your swap doesn't actually swap but also assigns i to the empty spot first.

You should make this explicit:

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

//actual swap again.
private static void Swap(int[] a, int i, int j) {
    var temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

After inlining the swap and forwarding the assigns this becomes:

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 + 1);
        a[i] = a[j];
        a[j] = i;
    }
    return a;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ i+1 or you'll never get 0 in index 0 :) \$\endgroup\$ – RobH Mar 16 '15 at 12:36
1
\$\begingroup\$

Just an another way:

int[] GetRandomizedArray(int n)
{
    return GetRandomizedEnumerable(n).ToArray();
}

IEnumerable<int> GetRandomizedEnumerable(int n)
{
    var random = new Random();
    var l = Enumerable.Range(0, n).ToList();
    foreach (var r in Enumerable.Range(0, n).Reverse().Select(i => random.Next(i + 1)))
    {
        yield return l[r];
        l.RemoveAt(r);
    }
}

A bit less performant, but easier to understand.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.