7
\$\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\$
4
  • 1
    \$\begingroup\$ More glaring is that solution 2 will always return the same array. \$\endgroup\$ Commented Mar 16, 2015 at 9:50
  • \$\begingroup\$ @ratchetfreak...mmm...that's not what I observed when running it... \$\endgroup\$ Commented Mar 16, 2015 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\$ Commented Mar 16, 2015 at 10:20
  • \$\begingroup\$ Name is not as good. I was just tweaking solution # 1 so I kept the method names. \$\endgroup\$ Commented Mar 16, 2015 at 11:09

5 Answers 5

11
\$\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\$
0
5
\$\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\$
0
4
\$\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
  • 1
    \$\begingroup\$ i+1 or you'll never get 0 in index 0 :) \$\endgroup\$
    – RobH
    Commented Mar 16, 2015 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\$
0
\$\begingroup\$

There are simpler ways to achieve this. For example:

new int[N].Select((s,i) => i + 1).OrderBy(o=> Guid.NewGuid()).ToArray();

Or

Enumerable.Range(0,N).Select(.....

This will be for a sequence of 1 to 10 with a randomised order

\$\endgroup\$
1
  • \$\begingroup\$ OP is asking for a better solution. If this is not a better solution, the onus is on OP or commenter like you to underline why this is not a better solution. OP considers his solution to be not ideal and is asking for a better solution That 10 is N is obvoius. \$\endgroup\$ Commented Mar 8 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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