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

Question

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?

More glaring is that solution 2 will always return the same array. — ratchet freak
– ratchet freak, Commented Mar 16, 2015 at 9:50
@ratchetfreak...mmm...that's not what I observed when running it... — user2858451
– user2858451, Commented Mar 16, 2015 at 9:52
Geh, method nameing tripped me up, I missed the temp=i in swap which makes it "not a swap". — ratchet freak
– ratchet freak, Commented Mar 16, 2015 at 10:20
Name is not as good. I was just tweaking solution # 1 so I kept the method names. — user2858451
– user2858451, Commented Mar 16, 2015 at 11:09

RobH · Accepted Answer · 2015-03-16 12:30:56Z

11

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.

edited Mar 16, 2015 at 12:30

answered Mar 16, 2015 at 12:16

RobH

17.1k6 gold badges38 silver badges73 bronze badges

Add a comment |

SirPython · Accepted Answer · 2015-12-14 00:08:40Z

5

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

edited Dec 14, 2015 at 0:08

SirPython

13.5k3 gold badges38 silver badges93 bronze badges

answered Dec 13, 2015 at 23:09

grashed

511 silver badge4 bronze badges

Add a comment |

ratchet freak · Accepted Answer · 2015-03-16 12:48:10Z

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;
}

\$\begingroup\$ i+1 or you'll never get 0 in index 0 :) \$\endgroup\$

RobH
– RobH

2015-03-16 12:36:28 +00:00
Commented Mar 16, 2015 at 12:36 — RobH
– RobH, Commented Mar 16, 2015 at 12:36

aush · Accepted Answer · 2015-03-16 20:24:41Z

1

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.

answered Mar 16, 2015 at 20:24

aush

6263 silver badges5 bronze badges

Add a comment |

Sᴀᴍ Onᴇᴌᴀ · Accepted Answer · 2024-03-08 23:58:20Z

0

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

edited Mar 8, 2024 at 23:58

Sᴀᴍ Onᴇᴌᴀ♦

29.6k16 gold badges46 silver badges203 bronze badges

answered Mar 8, 2024 at 4:03

Sriram Vanamamalai

111 bronze badge

\$\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\$

Sriram Vanamamalai
– Sriram Vanamamalai

2024-03-08 23:32:49 +00:00
Commented Mar 8, 2024 at 23:32

Add a comment |

Stack Exchange Network

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

5 Answers 5

You must log in to answer this question.

Linked

Hot Network Questions

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

5 Answers 5

You must log in to answer this question.

Linked

Related

Hot Network Questions