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

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

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

Если вы используете .NET 3.5, вы можете использовать следующие преимущества IEnumerable:

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();    

Изменить: и вот соответствующий код VB.NET:

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

Второе редактирование в ответ на замечания о том, что System.Random «не является потокобезопасным» и «подходит только для игрушечных приложений» из-за возврата временной последовательности: как используется в моем примере, Random () полностью потокобезопасен, если только вы разрешаете повторный ввод процедуры, в которой вы рандомизируете массив, и в этом случае вам все lock (MyRandomArray)равно понадобится что-то вроде того, чтобы не повредить ваши данные, что также будет защищать rnd.

Кроме того, следует хорошо понимать, что System.Random как источник энтропии не очень силен. Как указано в документации MSDN , System.Security.Cryptography.RandomNumberGeneratorесли вы делаете что-то, связанное с безопасностью , вам следует использовать что-то производное . Например:

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

В следующей реализации используется алгоритм Фишера-Йейтса, известный также как Knuth Shuffle. Он выполняется за O (n) раз и перемешивается на месте, поэтому он лучше работает, чем метод «сортировки случайным образом», хотя это больше строк кода. См. Здесь некоторые сравнительные измерения производительности. Я использовал System.Random, который подходит для не криптографических целей. *

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

Применение:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* Для более длинных массивов, чтобы сделать (чрезвычайно большое) количество перестановок равновероятным, потребуется запустить генератор псевдослучайных чисел (ГПСЧ) через множество итераций для каждого свопа, чтобы произвести достаточно энтропии. Для массива из 500 элементов только очень небольшая часть возможных 500! перестановки можно будет получить с помощью ГПСЧ. Тем не менее, алгоритм Фишера-Йейтса беспристрастен, поэтому перемешивание будет таким же хорошим, как и используемый вами ГСЧ.

Вы ищете алгоритм перетасовки, верно?

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

Тупой путь

• Создайте дубликат вашего первого массива, но пометьте каждую строку случайным числом.
• Отсортируйте повторяющийся массив по случайному числу.

Этот алгоритм работает хорошо, но убедитесь, что ваш генератор случайных чисел вряд ли пометит две строки одним и тем же номером. Из-за так называемого парадокса дней рождений это случается чаще, чем можно было ожидать. Его временная сложность O ( n log n ).

Умный способ

Я опишу это как рекурсивный алгоритм:

Чтобы перемешать массив размера n (индексы в диапазоне [0 .. n -1]):

если n = 0

• ничего не делать

если n > 0

• (рекурсивный шаг) перемешать первые n -1 элементов массива
• выберите случайный индекс x в диапазоне [0 .. n -1]
• поменять местами элемент с индексом n -1 на элемент с индексом x

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

Сложность по времени - O ( n ).

Этот алгоритм прост, но неэффективен, O (N ² ). Все алгоритмы «упорядочить по» обычно равны O (N log N). Вероятно, это не имеет значения для сотен тысяч элементов, но это будет для больших списков.

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

Причина, по которой это O (N ² ), тонкая: List.RemoveAt () - это операция O (N), если вы не удалите ее по порядку с конца.

Вы также можете сделать метод расширения из Мэтта Хауэллса. Пример.

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

Тогда вы можете просто использовать это как:

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

Просто подумав, вы могли бы сделать это:

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

Рандомизация массива требует значительных усилий, так как вам нужно переместить кучу строк. Почему бы просто не читать случайным образом из массива? В худшем случае вы даже можете создать класс-оболочку с помощью getNextString (). Если вам действительно нужно создать случайный массив, вы можете сделать что-то вроде

for i = 0 -> i= array.length * 5
   swap two strings in random places

* 5 произвольно.

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

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

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

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

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

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

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

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

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

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

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

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

Shuffle () - это расширение для любого IEnumerable, поэтому получение, скажем, чисел от 0 до 1000 в случайном порядке в списке может быть выполнено с помощью

Enumerable.Range(0,1000).Shuffle().ToList()

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

Вам не нужны сложные алгоритмы.

Всего одна простая строка:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

Обратите внимание, что нам нужно сначала преобразовать Arrayв List, если вы не используете Listв первую очередь.

Также учтите, что это неэффективно для очень больших массивов! В остальном все чисто и просто.

Это полное рабочее консольное решение, основанное на примере, приведенном здесь :

class Program
{
    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };

    static void Main()
    {
        var result = Shuffle(words1);
        foreach (var i in result)
        {
            Console.Write(i + " ");
        }
        Console.ReadKey();
    }

   static string[] Shuffle(string[] wordArray) {
        Random random = new Random();
        for (int i = wordArray.Length - 1; i > 0; i--)
        {
            int swapIndex = random.Next(i + 1);
            string temp = wordArray[i];
            wordArray[i] = wordArray[swapIndex];
            wordArray[swapIndex] = temp;
        }
        return wordArray;
    }         
}

        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();

Вот простой способ использования 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);

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