Shuffle list of strings consistently

Question

Using C# 6 I have a list of names alphabetically ordered:

List<String> names = getAlphabeticallyOrderedNames();

I need to shuffle the names but I want to get the same result every time. So I cannot use:

List<String> shuffledNames = names.OrderBy(x => Guid.NewGuid());

I then tried something like:

List<String> shuffledNames = names.OrderBy(x => "d2fda3b5-4089-43f9-ba02-f68d138dee49");

Or

List<String> shuffledNames = names.OrderBy(x => Int32.MaxValue);

But the names are not shuffled ...

How can I solve this?

Use the shuffler from [this answer](http://stackoverflow.com/a/1262619/106159), but use the overload of the `Random` constructor that takes a seed, and use the same seed each time. — Matthew Watson, Mar 23 '17 at 14:59
*.OrderBy(x => Guid.NewGuid());* I consider this to be a terrible hack, to be used in SQL or in some rare cases... — xanatos, Mar 23 '17 at 14:59
@xanatos In this case I am not using in SQL but sometimes I need to use it in SQL — Miguel Moura, Mar 23 '17 at 15:00
Yes, [don't use Guid.NewGuid() as a rng](https://blogs.msdn.microsoft.com/oldnewthing/20120523-00/?p=7553) — Matthew Watson, Mar 23 '17 at 15:01
The problem here is also "How Random is Random()?". Does this need to return the same sorted result *every* time the program is run when given the same values (so not really random) or can it vary between execution instances? Calling `Random()` with its overloaded constructor fits the second situation, but if the resultsets are always identical it might save processing power to implement something inheriting `IComparer` or `IComparable`. — CDove, Mar 23 '17 at 15:04
Yes, I need the same order every time I run the application. That is the objective — Miguel Moura, Mar 23 '17 at 15:05
Thinking about it, is the implementation of `Random` guaranteed to never change? Probably not... — Matthew Watson, Mar 23 '17 at 15:07
In that case, you could get by with something simpler, like ordering by the number of characters in the string plus the remainder when divided by some arbitrary integer. If you use the GUID or the hash value, you can't be guaranteed on your sort order. — CDove, Mar 23 '17 at 15:07
@MatthewWatson The documentation specifies the particular implementation used, and specifies that it will always produce the same sequence for the same version of .NET, but says that the sequence (for the same seed) is subject to change between .NET versions. — Servy, Mar 23 '17 at 15:09
@CDove Number of characters in the string? Which string? I have a list of Strings. Am I missing something? — Miguel Moura, Mar 23 '17 at 15:09
@MatthewWatson ; Imagine what would happen if the bitness of the .Net version changed and suddenly your Math.Random was checking a 128-bit span instead of a 32- or a 64-bit one. It's an obscure and rare thing, but an example of how such implementations can change with time. — CDove, Mar 23 '17 at 15:10
@MatthewWatson I will be fine if the order changes between NET versions ... — Miguel Moura, Mar 23 '17 at 15:10
@MiguelMoura I was referring to getting the string.Length of each of your strings, dividing them by *n* which is pretty much an integer you just make up arbitrarily, and adding the remainder (obtained with `%`) to the string.Length. ("Hello".Length + ("Hello".Length % 6) would be an example) — CDove, Mar 23 '17 at 15:13
I added an update with code that seems to solve the problem. Any comment? — Miguel Moura, Mar 23 '17 at 15:17
@MiguelMoura Your latest change is good - but note that you don't need to seed it with `Int32.MaxValue` - you can use any number, so long as you always use the same number when you intend to generate the same sequence. Also, it's not very efficient to sort a collection merely to shuffle it (sorting will be O(N.Log(N)) complexity rather than O(N) — Matthew Watson, Mar 23 '17 at 15:24

score 5 · Accepted Answer · edited May 23 '17 at 12:10

5

You can use a standard shuffle algorithm, such as the one from this answer:

Suitably modified to add a seed parameter, it would look like this:

public static void Shuffle<T>(IList<T> list, int seed)
{
    var rng = new Random(seed);
    int n = list.Count;

    while (n > 1)
    {
        n--;
        int k = rng.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

Then to shuffle in a repeatable way, just specify the same seed for the shuffle for each repeated shuffle:

List<String> names = getAlphabeticallyOrderedNames();
int seed = 12345;
Shuffle(names, seed);

edited May 23 '17 at 12:10

Community

1
1

answered Mar 23 '17 at 15:18

Matthew Watson

104,400
10
158
276

I am looking for an IEnumerable extension rather than to a IList and not changing the source but rather return a new one so it works like OrderBy. I added to updates, one based on your code, another using yield. Which one do you consider better? – Miguel Moura Mar 23 '17 at 16:06
@MiguelMoura I see that Update 3 is essentially the same as [this approach](http://stackoverflow.com/a/5807238/106159). I'd go with that one. It's also algorithmically the same as the shuffle algorithm I posted above. – Matthew Watson Mar 23 '17 at 17:48
I did a few unit tests and Update 3 seems to work fine ... Here it is: http://rextester.com/YMQP20157 – Miguel Moura Mar 23 '17 at 17:51
@MiguelMoura Yes, I think you should go with that! – Matthew Watson Mar 23 '17 at 17:53

score 1 · Answer 2 · answered Mar 23 '17 at 17:53

An Enumerable extension using Yield and having Seed value as parameter (Online Example):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Int32? seed = null) {

  List<T> buffer = source.ToList();

  Random random = seed.HasValue ? new Random(seed.Value) : new Random();

  Int32 count = buffer.Count;

  for (Int32 i = 0; i < count; i++) {          
    Int32 j = random.Next(i, count);
    yield return buffer[j];          
    buffer[j] = buffer[i];
  }

}

score 0 · Answer 3 · answered Mar 23 '17 at 15:01

0

Try ordering by the hash value

var shuffled = names.OrderBy(n=>n.GetHashCode());

answered Mar 23 '17 at 15:01

Connell.O'Donnell

3,603
11
27
61

Note that the hash of a string is not fixed... There is an option in [app.config/web.config](https://msdn.microsoft.com/en-us/library/jj152924.aspx) to randomize the "seed". – xanatos Mar 23 '17 at 15:04
1

This will be ok unless the OP wants to guarantee the same order for each run of the application. From MSDN: `"The hash code itself is not guaranteed to be stable. Hash codes for identical strings can differ across versions of the .NET Framework and across platforms (such as 32-bit and 64-bit) for a single version of the .NET Framework. In some cases, they can even differ by application domain. "` – Matthew Watson Mar 23 '17 at 15:04
I do want to guarantee the same order for each run of the application – Miguel Moura Mar 23 '17 at 15:04
Hashes aren't random, and subject to change on every single new execution of the program. – Servy Mar 23 '17 at 15:10

Shuffle list of strings consistently

3 Answers3