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

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

Отказ отвечать этим требованиям может вызвать любое количество проблем в программе сортировки включая возможность бесконечного цикла.

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

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

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

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

Генерируйте массив случайных плаваний или ints той же длины. Вид, которые выстраивают и делают соответствующие подкачки на Вашем целевом массиве.

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

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

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

Просто думая первое, что пришло на ум, Вы могли сделать это:

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, произвольно.

Этот алгоритм прост, но не эффективен, O (N <глоток> 2 ). Весь "порядок" алгоритмами обычно O (N, регистрируют 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 <глоток> 2 ) является тонкой: Список. RemoveAt () является O (N) операция, если Вы не удаляете в порядке от конца.

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

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

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

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

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

Хорошо, существует два способа сделать это: clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-all путь и dumb-as-rocks-but-who-cares-because-it-works путь.

Немой путь

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

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

Умный путь

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

Для перестановки массива размера n (индексы в диапазоне [0.. n-1]):

, если n = 0

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

, если n> 0

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

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

Временная сложность является O ( n).

Вы также можете создать метод расширения из Matt Howells. Пример.

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