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

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

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

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

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

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

Этот алгоритм прост, но неэффективен, 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), если вы не удалите ее по порядку с конца.

Если вы используете .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]);
    }

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

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

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

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

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

Тупой путь

• Create a duplicate of your first array, but tag each string should with a random number.
• Sort the duplicate array with respect to the random number.

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

Умный способ

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

To shuffle an array of size n (indices in the range [0..n-1]):

if n = 0

• do nothing

if n > 0

• (recursive step) shuffle the first n-1 elements of the array
• choose a random index, x, in the range [0..n-1]
• swap the element at index n-1 with the element at index x

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

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

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

Следующая реализация использует Алгоритм Фишера-Йейтса AKA 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! перестановки можно будет получить с помощью ГПСЧ. Тем не менее, алгоритм Фишера-Йейтса беспристрастен, и поэтому перемешивание будет таким же хорошим, как и используемый вами ГСЧ.

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

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

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

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

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

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

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

Вы также можете сделать метод расширения из 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>();

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

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

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