Fisher-Yates shuffle: Who is right, .NET 8 or Wikipedia?

Question

Was looking for shuffling an array from within Unity, remembered that .NET 8 has Random.Shuffle.

It turns out that the implementation is the Fisher-Yates algorithm.

But when looking at it and at Wikipedia page, they're not 100% identical.

public void Shuffle<T>(Span<T> values)
{
    int n = values.Length;

    for (int i = 0; i < n - 1; i++)
    {
        int j = Next(i, n);

        if (j != i)
        {
            T temp = values[i];
            values[i] = values[j];
            values[j] = temp;
        }
    }
}

Wikipedia, "inside-out" variant:

To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      if j ≠ i
          a[i] ← a[j]
      a[j] ← source[i]

The .NET version does everything within the if block, not Wikipedia's.

Question:

Which one of these is right and can you explain why it is?

Why did you pick the "inside-out" variant from the Wikipedia page? The algorithm .NET implemented is the one described in the "the modern algorithm" section of the Wikipedia page. — Sweeper
– Sweeper, Commented Mar 20, 2024 at 19:55
@Sweeper If you look at the modern algorithm, it differs significantly from .NET's. — aybe
– aybe, Commented Mar 20, 2024 at 19:58
No it is not. It's the one starting with "for i from 0 to n−2 do...". Perhaps the notation of the loop confused you? Notice the C# loop also loops from 0 to n - 2 - it's a < not <=. — Sweeper
– Sweeper, Commented Mar 20, 2024 at 20:02

trincot · Accepted Answer · 2024-03-20 20:04:24Z

2

As Wikipedia explains, this inside-out variant is initialising a target array that is different from the source array. The algorithm you quote from NET.8 is an inplace algorithm also described in the same Wikipedia article.

When a different array must receive the shuffled data, then an assignment has to happen to each index of the target array. This is why that assignment is not part of the conditional block.

The inplace algorithm can detect the situation where a value happens not to move and so the swap does not have to be executed.

The NET.8 version corresponds to what Wikipedia calls "An equivalent version which shuffles the array in the opposite direction". Admittedly Wikipedia performs the swap unconditionally. Of course, if i and j are the same this swap is a no-op, and apparently NET.8 coders have found that it is worth it to perform an extra if comparison in each iteration so to save on executing a swap when both indices are equal.

edited Mar 20, 2024 at 20:04

answered Mar 20, 2024 at 19:58

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

aybe Over a year ago

Now it's much more clear thanks to your explanations!

Peter - Reinstate Monica Over a year ago

As an aside, the branch is probably costlier than simply performing the swap for integers; it's likely there for more elaborate (value) types.

Collectives™ on Stack Overflow

Fisher-Yates shuffle: Who is right, .NET 8 or Wikipedia?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related