Clever way to shuffle a List<T> in one line of C# code

[Antistone]

@the_real_ijed

This is the method;

private List<GameObject> shuffleGOList(List<GameObject> inputList)
    {    //take any list of GameObjects and return it with Fischer-Yates shuffle
        int i = 0;
        int t = inputList.Count;
        int r = 0;
        GameObject p = null;
        List<GameObject> tempList = new List<GameObject>();
        tempList.AddRange(inputList);
     
        while (i < t)
        {
            r = Random.Range(0,tempList.Count);
            p = tempList[i];
            tempList[i] = tempList[r];
            tempList[r] = p;
            i++;
        }
     
        return tempList;
    }

So you’d add that first line in a method where you need a shuffled tempList and then access that as you need to.

I believe this is efficient, after reading the thread. Anything I missed please let me know

You’ve made an error in your implementation of Fisher-Yates. As written, you have a biased shuffle–you’ll get certain results more often than others. You want to change

r = Random.Range(0,tempList.Count);

to

r = Random.Range(i,tempList.Count);

So that once you’ve chosen a random element for the first position, it will stay there and not get swapped again while you are randomizing the rest of the list.

This is a common mistake. IIRC Unity even made this exact mistake in their own docs. (I reported it when I noticed, but I haven’t checked back to see if they fixed it.)

It may be hard to see why this would matter, but if you run some tests (shuffle the same original list a bunch of times, and count up how often each element ends up in each position) you’ll see that it does matter.

As a minor optimization, you could end your loop one iteration earlier, since once you’re down to the last element there’s only one choice left for what to put there. (In other words, shuffling a list of size 1 doesn’t require you to do anything.)

Also, I notice your function creates a copy of the list, shuffles the copy, and returns the copy. I’d say it’s more useful to have a function that shuffles a list in-place, without copying anything. If the caller wants to preserve the original, they can easily make a copy themselves before calling your function. But often, you don’t need the original anymore, in which case you’d rather not have to pay for the copy operation.

[Cameron_SM]

@Smooth_P

Actually, this is likely going to be O(n²) time complexity and O(n) space complexity with two new lists created as well as other temporary objects.

Most of the time I’d counter that with “not likely to be a performance critical task” but in this case, shuffle is a solved problem with common well understood solutions so yeah, use I’d say use the known solutions unless you have a specific reason not to.

[sneauxwolfe]

Wow! I just came here looking for a way to stick a List shuffle method inside a scriptable object. I received a heck of an education!

[Labuzzz]

@Smooth_P

Actually, this is likely going to be O(n²) time complexity and O(n) space complexity with two new lists created as well as other temporary objects.

If your collection implements IList (eg: T[ ], List) it would be much better to do an in-place shuffle with an extension method:

(This code is from Smooth.Foundations, which I will be submitting to the asset store as a free-to-use, free-to-distribute package as soon as I finish cleaning some things up and complete the autodocs.)

public static class IListExtensions {
    /// <summary>
    /// Shuffles the element order of the specified list.
    /// </summary>
    public static void Shuffle<T>(this IList<T> ts) {
        var count = ts.Count;
        var last = count - 1;
        for (var i = 0; i < last; ++i) {
            var r = UnityEngine.Random.Range(i, count);
            var tmp = ts[i];
            ts[i] = ts[r];
            ts[r] = tmp;
        }
    }
}

Very good move!
Many thanks!

[Bunny83]

It seems it’s time to lock this thread since it gets necroed every couple of month just for a “thank you” post. You can simply “like” a post and call it a day. There’s no need to push an ancient thread to the top for no reason.

[eisenpony]

I realize it’s against the unwritten etiquette, but I really like this characteristic of forums. I’d argue, if it weren’t for the 2020 necro, much of the value in this thread wouldn’t exist. Good conversations deserve to bubble up to the front page now and again. Let’s not rush to turn everything into stack overflow!

[Bunny83]

@eisenpony

I realize it’s against the unwritten etiquette, but I really like this characteristic of forums. I’d argue, if it weren’t for the 2020 necro, much of the value in this thread wouldn’t exist. Good conversations deserve to bubble up to the front page now and again. Let’s not rush to turn everything into stack overflow!

Of course and I’m absolutely not against a constructive addition or a correction of misleading, outdated or wrong information. However bringing a thread to the top without any useful addition just clutters the forum and draws attention away from actual relevant topics. I’m also usually against closing threads for exactly those reasons. However we have countless threads where the last constructive contribution was like 7 years ago and those threads gets “thank you” bumps every couple of month.

A closed thread is not really the end of the story. If a topic becomes relevant again for someone and he has new information, there’s always the possibility to create a new thread and link to the old one in the first post and add the new information there. We do have some threads with 30+ pages which are almost useless because almost nobody will go though 30 pages (I did a couple of times ^^). It’s great to have such conversations conserved, however the chances of finding the right information in a pile of pages goes down as the number of pages go up. It’s way better to have seperate threads with good descriptive titles and that they are focused on the topic.

On Unity Answers there were a couple of comments on old questions or answers that a documentation link or wiki link is dead. I’ll appreciate such comments and I usually edit the original post and fix the link (archive.org for the rescue). Yes, that will bump the question, but we actually add / fix the information provided and that’s perfectly fine.

[Baste]

Honestly, the big problem here is that if somebody googles “Unity shuffle list”, they might get to this thread, only read the first post with the snazzy one-liner, copy it, and not read all the posts from later on explaining how OP’s sorting algo is shit.

So to provide the most utility for developers (especially devs that are new enough to not just know about fisher-yates already), some moderator should probably edit the first post to say “this code’s the worst, don’t use it”.

[eisenpony]

At the risk of taking this thread off topic, and ironically getting it locked while arguing that it should stay open , I have just one more comment …

I reiterate my POV that

@eisenpony

Good conversations deserve to bubble up to the front page now and again.

Perhaps I’m just out of touch, and this happens so often that the main result is

@Bunny83

However bringing a thread to the top without any useful addition just clutters the forum and draws attention away from actual relevant topics.

But I don’t really think so

I agree linking to an old post is an option, but it is a bit clumsy, especially for a new comer.

While 30+ pages is probably not going to get read by anyone, the first page or two likely will. And every once in a while, someone will read all those pages and likely get an education or a lot of cheap entertainment. Anyways, that seems besides the point because I’ve never seen 30+ pages of thank-yous.

@Baste

Honestly, the big problem here is that if somebody googles “Unity shuffle list”, they might get to this thread, only read the first post with the snazzy one-liner, copy it, and not read all the posts from later on explaining how OP’s sorting algo is S***.

While the main thrust of your point is true, I’ll disagree that this is a big problem. In my view, a big problem is that people like @Bunny83 and @Baste have an incredibly rich understanding of concepts that is only ever really seen by people who would really benefit, like @sneauxwolfe , when they get fired up about a topic; when they get into the details of why a suggested idea is good or bad.

As a forum is “a place, meeting, or medium where ideas and views on a particular issue can be exchanged.”, I really really like when I see different perspectives getting exchanged, and even people getting a little heated about their ideas.

What I noticed about this thread (admittedly, not all are like this) is that the first necro post, while breaking all the rules, brought a real wealth of information to the forum. A discussion that, I believe, would not have occurred in a thread where one person asks a question and one person gives an answer (the majority of threads).

[MelvMay]

Everyone has their opinion however luckily it can be settled by the Community Code of Conduct which clearly states:

1i. Pointless necroposting (posting in a forum thread that is too old to matter any more, or has served its purpose)

Some people won’t tidy their house or throw anything away just in-case it might be useful one day. Luckily closing a thread isn’t throwing it away. Devs can still hit like if it helped them or as said above, it doesn’t stop devs creating their own thread with their “revelations”.

[hippocoder]

That’s true but Pointless is the clause which renders some necro posting useful, so YMMV! Otherwise we would auto-lock all threads a couple of years after the final post. And even then the necro window would shift to a year, then 6 months, then 3 months, or whatever window pointless falls into.

So whoever locks a thread through that Code of Conduct is applying their own view of Pointless.

[MelvMay]

Yep, it’s subjective based upon experience and making a judgement call and understanding how threads like this go. They turn into an endless debate, end up hijacking the thread and going well off-topic. That in itself here is a good reason to close it.

Feel free to reopen it if you consider this a super valuable thread though that has had anything useful added to it this year. I don’t wish to debate a word now.