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

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

120 голосов
/ 20 сентября 2008

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

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

Ответы [ 18 ]

181 голосов
/ 21 сентября 2008

Следующая реализация использует алгоритм Фишера-Йейтса . Он выполняется за 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};
new Random().Shuffle(array);

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

149 голосов
/ 20 сентября 2008

Если вы используете .NET 3.5, вы можете использовать следующую крутость IEnumerable (VB.NET, а не C #, но идея должна быть ясной ...): 

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]);
    }
16 голосов
/ 20 сентября 2008

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

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

Тупой путь

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

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

Умный путь

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

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

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

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

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

8 голосов
/ 20 сентября 2008

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

4 голосов
/ 18 августа 2010

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

   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>();
1 голос
/ 20 сентября 2008

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

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

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

1 голос
/ 20 сентября 2008

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

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);
}
0 голосов
/ 13 апреля 2016

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

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;
    }         
}
0 голосов
/ 13 апреля 2015

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

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

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

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

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

0 голосов
/ 24 октября 2012

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

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

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

Страница:
...