Как случайным образом перемешать список List<T> в C#?

Алгоритм Фишера-Йетса (Knuth shuffle) для перемешивания List<T>

Ваша интуиция насчёт алгоритма Фишера-Йетса абсолютно верна. Это стандартный и самый эффективный способ случайного перемешивания (shuffle) списка. Он работает за O(n) времени и O(1) дополнительной памяти.

Вот правильная реализация для List<T>:

public static void Shuffle<T>(List<T> list)
{
    Random rng = new Random();
    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;
    }
}

Как это работает:

• Мы идём по списку с конца к началу (или наоборот, как в примере).
• Для каждого элемента с индексом n выбираем случайный индекс k от 0 до n включительно.
• Меняем местами элементы с индексами k и n.
• Таким образом, каждый элемент гарантированно оказывается на новой позиции с равной вероятностью.

Ваша ошибка была в том, что вы просто копировали значение, не сохраняя оригинальное. В правильной реализации мы используем временную переменную value для обмена.

Улучшенная версия с использованием расширяющего метода

Чтобы сделать код более удобным, можно оформить перемешивание как extension method:

public static class ListExtensions
{
    private static readonly Random _rng = new Random();

    public static void Shuffle<T>(this IList<T> list)
    {
        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;
        }
    }
}

// Использование:
List<Card> deck = new List<Card>();
// ... заполняем колоду ...
deck.Shuffle();

Потокобезопасная версия

Если ваш код выполняется в многопоточной среде, стандартный Random не является потокобезопасным. Вот два решения:

Вариант 1: Использовать локальный Random для каждого потока

public static void ShuffleThreadSafe<T>(IList<T> list)
{
    Random localRng = new Random(Guid.NewGuid().GetHashCode()); // Уникальная инициализация
    int n = list.Count;
    while (n > 1)
    {
        n--;
        int k = localRng.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

Вариант 2: Использовать ThreadLocal<Random>

private static readonly ThreadLocal<Random> _threadLocalRng = 
    new ThreadLocal<Random>(() => new Random(Guid.NewGuid().GetHashCode()));

public static void ShuffleThreadSafe<T>(IList<T> list)
{
    Random rng = _threadLocalRng.Value;
    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;
    }
}

Важные замечания

• Не создавайте новый Random каждый раз при вызове метода — это может привести к одинаковым последовательностям, если вызовы происходят быстро (из-за одинакового seed на основе времени).
• Для криптографически стойкого перемешивания (например, в онлайн-казино) используйте System.Security.Cryptography.RandomNumberGenerator.
• Алгоритм работает только с изменяемыми коллекциями (List, массивы). Для неизменяемых коллекций нужно сначала создать копию.

Вот пример для вашей карточной игры:

public class Card
{
    public string Suit { get; set; }
    public string Rank { get; set; }
}

// Использование
List<Card> deck = CreateDeck(); // Ваш метод создания колоды
deck.Shuffle(); // Теперь колода перемешана!

Random rng = new Random();
List<int> shuffled = numbers
    .OrderBy(x => rng.Next())
    .ToList();