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

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:

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.

12 Likes

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

LinQ throws up some extra garbage for the GC as well, so avoid unless you're doing it at a low frequency.

3 Likes

thanks

Simplest way to “Shuffle” is just to order by random guid, I actually did this for a job code interview.

// Say we have listOfThings filled with things.
var listOfThings = new List<string>()
{
   "1", "2", "3", "4"
};
// Randomly Order it by Guid..
listOfThings = listOfThings.OrderBy(i => Guid.NewGuid()).ToList();
// 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)

1 Like

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.

6 Likes

If you write the fisher-yates shuffle extension method and just call that it's also "one line of code" ¯_(ツ)_/¯

1 Like

Like Smooth-P's extensions method.

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.

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.

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:

lst.Shuffle();

OR

What @Kurt-Dekker said

3 Likes

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.

Isn’t that more related to how “random” your random function is? If the distribution is completely uniform, the sorting method shouldn’t matter.

1 Like

[quote=“Boz0r, post:13, topic: 535113, username:Boz0r”]
Isn’t that more related to how “random” your random function is? If the distribution is completely uniform, the sorting method shouldn’t matter.
[/quote]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.

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.

1 Like

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.

1 Like

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.

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.

I’m with you there, That was my original point. :slight_smile: (If values aren’t unique we only have a partial order)

This will return a shuffled version of any list you point it at;

List<GameObject> tempList = shuffleGOList(yourList);

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(i,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 :)

EDIT: Fixed the issue pointed out by Antistone in the method.