c# pass-by-reference Fisher-Yates Shuffler

Question

I am trying to use the Fisher-Yates algorithm to shuffle a stack of elements. I'm having trouble passing in the stack by reference. The code below gives the error "Iterators cannot have ref or out parameters". How do I get the algorithm to act on the actual stack that gets passed in?

Thanks.

Code is below.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
public static class Doshuffle
{
    public static IEnumerable<T> Shuffle<T>(ref Stack<T> source)
    {

        Random rng = new Random();
        T[] elements = source.ToArray();
        source.Clear();
        // Note i > 0 to avoid final pointless iteration
        for (int i = elements.Length - 1; i > 0; i--)
        {
            // Swap element "i" with a random earlier element it (or itself)
            int swapIndex = rng.Next(i + 1);
            T tmp = elements[i];
            elements[i] = elements[swapIndex];
            elements[swapIndex] = tmp;
        }
        // Lazily yield (avoiding aliasing issues etc)
        foreach (T element in elements)
        {
            source.Push(element);
            yield return element;
        }
    }
}

}

use Jon's: http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm — Mitch Wheat, Aug 22 '11 at 04:18
You don't need `ref` but I'd almost say leave it in. The combination of returning an `IEnumerable` _and_ modifying the incoming collection is rather fishy. — H H, Aug 22 '11 at 09:05

score 7 · Accepted Answer · edited May 23 '17 at 09:59

How do I get the algorithm to act on the actual stack that gets passed in?

You do not need a ref parameter here since Stack<T> is a reference type and you are not trying to re-assign the reference itself.

References are by default passed by value but that value (the reference) points to the same object on the heap, in other words you have two references pointing to the same object which is fine - all operations will be executed on the original Stack<T> object.

Edit:

In light of your comment I suggest you redesign to not modify the original Stack<T> which is troublesome to begin with:

public static IEnumerable<T> Shuffle<T>(Stack<T> source)
{
    Random rng = new Random();
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

Now you can just use it like this:

foreach (var item in Doshuffle.Shuffle(gameDeck)) 
{ 
   System.Console.WriteLine(item.cardName); 
}

Also be careful with your use of Random - you might want to pass it in. At this point you can use Jon Skeet's Shuffle implementation instead of your own - it's better to reuse than reinvent.

Final Edit:

It looks like you just want to shuffle your Stack<T> in place -use an extension method instead:

public static void Shuffle<T>(this Stack<T> source)
{
    Random rng = new Random();
    T[] elements = source.ToArray();
    source.Clear();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    foreach (T element in elements)
    {
        source.Push(element);
    }
}

Now you can just do:

gameStack.Shuffle();

Why then does the following code show me the stack in it's original form? `Doshuffle.Shuffle(gameDeck);` `foreach (var item in gameDeck) { System.Console.WriteLine(item.cardName); }` — Ojen, Aug 22 '11 at 14:12
@FrankAMan: I think you misunderstood how iterator blocks / yield works in C#: The results are evaluated lazily - unless you iterate over the results of `DoShuffle()` or do something like `Doshuffle.Shuffle(gameDeck).ToList()` your iterator block wont' even start and your gameDeck is not cleared. — BrokenGlass, Aug 22 '11 at 14:56
Thank you for the help. I based my version off of Jon Skeet's post. I just need something where I can call `Doshuffle.Shuffle(gameDeck);` and the gameDeck (which is a stack) is shuffled. Instead of returning each element, I want the original stack to be modified. Is seems like in your approach I have to use the foreach loop to actually get the deck to shuffle. Is there another approach I should be taking? — Ojen, Aug 22 '11 at 16:29
Thank you, for the further detail. This works nicely, and for all my different stacks! It looks like I should have stayed away from having the IEnumerable return type. — Ojen, Aug 22 '11 at 18:23

score 4 · Answer 2 · answered Aug 22 '11 at 04:19

The stack does not need to be passed by reference like that because reference types (like Stack<T>) are already passed by reference. The only reason to use ref or out modifiers on a reference parameter is if you want to actually modify the reference itself (such as creating a new Stack<T> and assigning it to the parameter as a sort of alternate method of return -- same as double pointers in C).

score 1 · Answer 3 · answered Aug 22 '11 at 04:19

1

Since Stack is a class, I don't think you need the ref keyword in this case.
It should work without it.

answered Aug 22 '11 at 04:19

Gishu

134,492
47
225
308

c# pass-by-reference Fisher-Yates Shuffler

3 Answers3