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

}

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. — Henk Holterman
– Henk Holterman, Commented Aug 22, 2011 at 9:05

Community · Accepted Answer · 2017-05-23 09:59:05Z

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); }
@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.
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?
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<T> return type.

siride · Accepted Answer · 2011-08-22 04:19:05Z

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).

Gishu · Accepted Answer · 2011-08-22 04:19:12Z

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

Collectives™ on Stack Overflow

c# pass-by-reference Fisher-Yates Shuffler

3 Answers 3

5 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Linked

Related