Лучший способ рандомизировать массив с .NET

Question

Каков наилучший способ рандомизировать массив строк с помощью .NET? Мой массив содержит около 500 строк, и я хотел бы создать новый Array с теми же строками, но в случайном порядке.

Пожалуйста, включите пример C # в ваш ответ.

Answer 1

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }  
    return sortedList;
}

Answer 2

На этот пост уже получен хороший ответ - используйте реализацию Дюрстенфельда в случайном порядке Фишера-Йейтса для быстрого и непредвзятого результата. Были даже опубликованы некоторые реализации, хотя я отмечаю, что некоторые из них на самом деле неверны.

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

Answer 3

Вот простой способ использования OLINQ:

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

Answer 4

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

Answer 5

Этот код перемешивает числа в массиве.

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }

Answer 6

Jacco, ваше решение для нестандартного IComparer небезопасно. Процедуры сортировки требуют, чтобы компаратор соответствовал нескольким требованиям для правильной работы. Первым среди них является последовательность. Если компаратор вызывается для одной и той же пары объектов, он всегда должен возвращать один и тот же результат. (сравнение также должно быть транзитивным).

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

Что касается решений, которые связывают случайное числовое значение с каждой записью, а затем сортируют по этому значению, это приводит к внутреннему смещению в выходных данных, поскольку каждый раз, когда двум записям присваивается одно и то же числовое значение, случайность выходных данных будет быть скомпрометированным. (В «стабильной» процедуре сортировки, какой бы ни был первый на входе, он будет первым на выходе. Array.Sort не является стабильным, но все еще существует смещение, основанное на разделении, выполненном алгоритмом быстрой сортировки).

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

Для перетасовки списка песен нет проблем с использованием засеянного PRNG (например, System.Random). Для покерного сайта это даже не вариант, и вам нужно думать о проблеме намного сложнее, чем кто-либо собирается сделать для вас в stackoverflow. (использование криптографического ГСЧ - это только начало, вам нужно убедиться, что ваш алгоритм не вносит смещения, что у вас достаточно источников энтропии и что вы не выставляете какое-либо внутреннее состояние, которое может поставить под угрозу последующую случайность).

Answer 7

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();

Answer 8

Создание массива случайных чисел с плавающей точкой или целых чисел одинаковой длины. Сортируйте этот массив и выполните соответствующие замены в целевом массиве.

Это дает действительно независимую сортировку.