Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

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

Discussion in 'Scripting' started by casimps1, Apr 16, 2014.

Thread Status:
Not open for further replies.
  1. casimps1

    casimps1

    Joined:
    Jul 28, 2012
    Posts:
    254
    I had been planning on writing a fairly traditional shuffle algorithm for my generic Lists when I ran across this clever little trick on another site. It uses System.Linq and lambda expressions to do the magic in one nice clean line:

    Code (csharp):
    1. shuffledList = myList.OrderBy( x => Random.value ).ToList( );
    Just thought I'd share this little shortcut.

    Also feel free to tell me why doing it this way is a horrible idea. :)

    I know it's somewhat inefficient (it is after all actually doing a true sort rather than a shuffle, so technically we're talking about going from O(n) to O(n log n) in complexity) so YMMV... but as long as you're not shuffling lists of massive size every frame it shouldn't matter at all.
     
    yong2khoo, Deeje, Novack and 9 others like this.
  2. Smooth-P

    Smooth-P

    Joined:
    Sep 15, 2012
    Posts:
    214
    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<T> (eg: T[], List<T>) 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.)

    Code (csharp):
    1.  
    2. public static class IListExtensions {
    3.     /// <summary>
    4.     /// Shuffles the element order of the specified list.
    5.     /// </summary>
    6.     public static void Shuffle<T>(this IList<T> ts) {
    7.         var count = ts.Count;
    8.         var last = count - 1;
    9.         for (var i = 0; i < last; ++i) {
    10.             var r = UnityEngine.Random.Range(i, count);
    11.             var tmp = ts[i];
    12.             ts[i] = ts[r];
    13.             ts[r] = tmp;
    14.         }
    15.     }
    16. }
    17.  
     
    Last edited: Apr 16, 2014
  3. JamesLeeNZ

    JamesLeeNZ

    Joined:
    Nov 15, 2011
    Posts:
    5,616
    LinQ throws up some extra garbage for the GC as well, so avoid unless you're doing it at a low frequency.
     
    halley, paulo_aa_pereira and MGGDev like this.
  4. Rockaso

    Rockaso

    Joined:
    Oct 31, 2016
    Posts:
    85
    thanks
     
  5. Eiznek

    Eiznek

    Joined:
    Jun 9, 2011
    Posts:
    374
    Simplest way to "Shuffle" is just to order by random guid, I actually did this for a job code interview.

    Code (CSharp):
    1. // Say we have listOfThings filled with things.
    2. var listOfThings = new List<string>()
    3. {
    4.    "1", "2", "3", "4"
    5. };
    6. // Randomly Order it by Guid..
    7. listOfThings = listOfThings.OrderBy(i => Guid.NewGuid()).ToList();
    8. // It's now shuffled.
    I read all about fisher yates before just implementing this, I don't completely remember, but I think there isn't much difference between the two? (I did get that job)
     
    Dryn27 likes this.
  6. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    I love when people reduce something to "a line of code" forgetting that their line of code is actually calling multiple functions that do a lot of the heavy lifting for you and result in more work being done then if you just wrote out what you're doing (and that could be encapsulated into its own method itself to make a "single line of code").

    I also fail to see how sorting on a guid is the "simplest" relative to sorting on Random.value. They're both random values. How is one simpler than the other? In what aspect? I mean... one could argue Guid.NewGuid is more complex since the algorithm for generating a guid is more complex than the algorithm for getting the next random value in a sequence. Of course one could argue that because Random.value must maintain a state it's more complex in the form of memory foot print... even though we're talking in the couple of bytes.

    I don't know... call me weird. But I do the same approach posted 6 years ago by Smooth-P. Seems pretty simple to me, as well as being the most efficient of the lot (I believe it's called the Fisher-Yates shuffle).

    I should point out also that said algorithm creates what is known as an "unbiased permutation"... it means that all permutations of the shuffle have equal odds. As opposed to the OrderBy(random) which is biased due to the fact it exploits the underlying QuickSort algorithm and done repeatedly results in a pattern of permutations that are favored over others. So not only is it more time complex, but it results in less statistical variation... which in most games doesn't matter. But if say you were creating a game for gambling (which Unity doesn't allow without a special license), the algorithm actually wouldn't meet the regulatory requirements of most state gambling boards.
     
    Last edited: Apr 21, 2020
  7. PraetorBlue

    PraetorBlue

    Joined:
    Dec 13, 2012
    Posts:
    7,893
    If you write the fisher-yates shuffle extension method and just call that it's also "one line of code" ¯\_(ツ)_/¯
     
    Bunny83 likes this.
  8. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    Like Smooth-P's extensions method.
     
  9. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    38,520
    Yes, I'm with you duct (and by extension I'm with Smooth-P as well)... there is no value in packing everything into one line, especially chained Linq statements.

    Putting all your code on one line only says:

    "I would like to hide all possible future bugs and malfunctions inside code that makes it extremely irritating to actually find the bug, code which will cause me to have to post non-line-wrapped 256-character lines of parenthesis and dot-infested nightmare code to the Unity forums saying that I have a null reference exception somewhere on that line and I can't find it."

    Just don't do it. You're NOT fooling anyone (certainly not the compiler) and you're wasting your own time first and foremost.
     
  10. Eiznek

    Eiznek

    Joined:
    Jun 9, 2011
    Posts:
    374

    It's high level coding, As a developer constantly create more and more tools until my code is increasingly simplified. It's just like using c# over using c++, it's a higher level language. No longer dealing with pointers, and addresses.

    As you become more fluent in your language you'd want these assists. It helps you get to your overall goal that much faster. No need to constantly recreate the wheel.
     
  11. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    Nothing in my post said reusable code was bad. Reusable code is fantastic.

    I was criticizing reducing code to a single line while not understanding what's going on underneath. That single line of code exploiting QuickSort algorithm which results in a less efficient O(NlogN) to as much as O(N^2) operation that has a biased set of results. Where as Smooth-P's approach utilizes a known good O(N) algorithm (fisher-yates) done up as an extension method (so it's reusable) and can be written in a single line of code on use:
    Code (csharp):
    1. lst.Shuffle();
    OR

    What @Kurt-Dekker said
     
    Bunny83 and Boz0r like this.
  12. Owen-Reynolds

    Owen-Reynolds

    Joined:
    Feb 15, 2012
    Posts:
    1,992
    It may not be fair: if you shuffle {1,2,3,4,....10} fairly, any number should have a 10% chance of being in any slot. Depending on the exact sort method (quick sort, but bubble for <20?) numbers may not move very far from their starting position, or may tend to fall into some other pattern.
     
  13. Boz0r

    Boz0r

    Joined:
    Feb 27, 2014
    Posts:
    419
    Isn't that more related to how "random" your random function is? If the distribution is completely uniform, the sorting method shouldn't matter.
     
    PraetorBlue likes this.
  14. Cannist

    Cannist

    Joined:
    Mar 31, 2020
    Posts:
    64
    That is only true if the assignment of random values induces a total order, i.e. each of the elements gets a different random number assigned.As soon as you have duplicates it's up to the sorting algorithm to break the ties.
     
  15. Owen-Reynolds

    Owen-Reynolds

    Joined:
    Feb 15, 2012
    Posts:
    1,992
    The first example, 6 years ago , used Random.value, which is a coin flip -- each time you compare items they roll 0-1 for themselves, highest wins. Compare again, and they each roll again. Since Bubble sort swap side-by-side items, the fist item has a 50% chance to stay in place, 25% to move up by only 1, 12.5% to move up 2 spaces... . C#'s sort says it uses Insertion sort for 16 or fewer items (but C# docs are often wrong). That gives us the same problem -- in an insertion sort, item 10 compares itself with items 9,8,7... until it finds a smaller one, so it still uses a coin flip to move 1 space, and won't move very far.

    Sure, the guid idea will sort of work (I'm assuming there's a hash involved, and hashes are purposely designed to look random). Assigning a constant "random" value to each item will give a random-seeming shuffle. But only once. You're probably going to want to shuffle again.
     
  16. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    Not so true, as @Owen-Reynolds pointed out in his last post.

    This is what I was talking about in my prior posts when I said that it will create a 'biased' result.

    You can see a description here on the Fisher-Yates wikipedia article about using sort on random value here:
    https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Sorting

    Because because the Random.value is uniform, it basically causes the sorting algorithm to express its algorithm in your results.

    Note that the "variant of the above" is referring to this paragraph:
    Basically if you were to assign unique random values to each element, and then sort, this would be completely suitable. But that's not what passing an RNG into a sort method does.
     
    Cannist likes this.
  17. Cannist

    Cannist

    Joined:
    Mar 31, 2020
    Posts:
    64
    Indeed I had missed that in the first post a random value was assigned each time the element would be inspected by the sorting algorithm. Thanks for clarifying.

    If I wanted to nitpick I could still uphold my claim that if a total order is induced the assignment of random numbers the sorting algorithm would not introduce any bias. In all the counter examples we do not have a total order. But really, I just missed that we assign multiple different random values to the same element.
     
  18. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    It's not that multiple values to the same element every time it's inspected. But also the values aren't unique across the set which means that ties won't result in an actual "random" shift, it'll always shift in the direction the algorithm does. Which also would end up statistically expressing itself.

    A constant random value needs to be assigned to each element, and that value has to be unique across the entire set. (which is what the wiki article I quoted is saying). Then, yes, sorting on a random value will work.

    So if you had:
    A, B, C, D

    And you assigned:
    44, 243, 112, 6 (random byte)

    That'd be fine.

    But if you assigned
    3,1,2,1 (random range 1-4)

    Not fine, because 1 and 1 would tie, and the sort algorithm would shift B and D based on its rules, and not on an actual randomness (may it be it takes first, takes, second, whatever... depends on the algorithm). This would introduce a bias as well.

    Thing is... how do you get a unique random set? Most simple algorithms out there suggest, get this, to fill a list with unique values and then shuffle them. lol.

    This is why technically the Guid.NewGuid work can technically be ever so slightly better than Random.value in regards to uniqueness, because technically the values are unique across the entire set. But you'd still be pulling non-unique values per element. Which honestly... I don't know personally how much bias that would introduce, but as I stated in my original post in regards to that one... it's more expensive than the solution Smooth-P posted both in time complexity, and just because generating a Guid is more expensive than generating a random value. But with that all said, where the guid falls short in this discussion of bias is that guids aren't uniform across the set, they're only unique.
     
    Last edited: Apr 22, 2020
  19. Cannist

    Cannist

    Joined:
    Mar 31, 2020
    Posts:
    64
    I'm with you there, That was my original point. :) (If values aren't unique we only have a partial order)
     
  20. the_real_ijed

    the_real_ijed

    Joined:
    Dec 6, 2012
    Posts:
    7
    This will return a shuffled version of any list you point it at;

    Code (CSharp):
    1. List<GameObject> tempList = shuffleGOList(yourList);
    This is the method;
    Code (CSharp):
    1. private List<GameObject> shuffleGOList(List<GameObject> inputList)
    2.     {    //take any list of GameObjects and return it with Fischer-Yates shuffle
    3.         int i = 0;
    4.         int t = inputList.Count;
    5.         int r = 0;
    6.         GameObject p = null;
    7.         List<GameObject> tempList = new List<GameObject>();
    8.         tempList.AddRange(inputList);
    9.      
    10.         while (i < t)
    11.         {
    12.             r = Random.Range(i,tempList.Count);
    13.             p = tempList[i];
    14.             tempList[i] = tempList[r];
    15.             tempList[r] = p;
    16.             i++;
    17.         }
    18.      
    19.         return tempList;
    20.     }
    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 :)

    EDIT: Fixed the issue pointed out by Antistone in the method.
     
    Last edited: Sep 17, 2021
  21. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    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
    Code (CSharp):
    1. r = Random.Range(0,tempList.Count);
    to
    Code (CSharp):
    1. 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.
     
  22. Cameron_SM

    Cameron_SM

    Joined:
    Jun 1, 2009
    Posts:
    915
    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.
     
    Last edited: Sep 17, 2021
  23. sneauxwolfe

    sneauxwolfe

    Joined:
    Jun 24, 2020
    Posts:
    2
    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!
     
    Adriano21 and martinakdani_unity like this.
  24. Labuzzz

    Labuzzz

    Joined:
    Mar 5, 2022
    Posts:
    2
    Very good move! ;)
    Many thanks! :cool:
     
  25. Bunny83

    Bunny83

    Joined:
    Oct 18, 2010
    Posts:
    3,919
    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.
     
  26. eisenpony

    eisenpony

    Joined:
    May 8, 2015
    Posts:
    974
    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 likes this.
  27. Bunny83

    Bunny83

    Joined:
    Oct 18, 2010
    Posts:
    3,919
    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.
     
    eisenpony likes this.
  28. Baste

    Baste

    Joined:
    Jan 24, 2013
    Posts:
    6,294
    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***.

    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 and Bunny83 like this.
  29. eisenpony

    eisenpony

    Joined:
    May 8, 2015
    Posts:
    974
    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
    Perhaps I'm just out of touch, and this happens so often that the main result is
    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.


    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).
     
    Bunny83 likes this.
  30. MelvMay

    MelvMay

    Unity Technologies

    Joined:
    May 24, 2013
    Posts:
    11,321
    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".
     
    Bunny83 likes this.
  31. hippocoder

    hippocoder

    Digital Ape

    Joined:
    Apr 11, 2010
    Posts:
    29,723
    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.
     
    Bunny83 and eisenpony like this.
  32. MelvMay

    MelvMay

    Unity Technologies

    Joined:
    May 24, 2013
    Posts:
    11,321
    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. ;)
     
    Bunny83 likes this.
Thread Status:
Not open for further replies.