Cara terbaik untuk mengacak array dengan .NET

Apa cara terbaik untuk mengacak array string dengan .NET? Array saya berisi sekitar 500 string dan saya ingin membuat yang baru Arraydengan string yang sama tetapi dalam urutan acak.

Harap sertakan contoh C # dalam jawaban Anda.

Jika Anda menggunakan .NET 3.5, Anda dapat menggunakan kesejukan IEnumerable berikut (VB.NET, bukan C #, tetapi idenya harus jelas ...):

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

Edit: OK dan ini kode VB.NET yang sesuai:

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

Suntingan kedua, sebagai tanggapan terhadap komentar bahwa System.Random "tidak threadsafe" dan "hanya cocok untuk aplikasi mainan" karena mengembalikan urutan berbasis waktu: seperti yang digunakan dalam contoh saya, Random () sangat aman untuk thread, kecuali Anda mengizinkan rutin di mana Anda mengacak array untuk dimasukkan kembali, dalam hal ini Anda akan memerlukan sesuatu seperti lock (MyRandomArray)itu agar tidak merusak data Anda, yang akan melindungi rndjuga.

Juga, harus dipahami bahwa System.Random sebagai sumber entropi tidak terlalu kuat. Seperti dicatat dalam dokumentasi MSDN , Anda harus menggunakan sesuatu yang berasal dari System.Security.Cryptography.RandomNumberGeneratorjika Anda melakukan sesuatu yang berhubungan dengan keamanan. Sebagai contoh:

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

Implementasi berikut menggunakan algoritma Fisher-Yates AKA the Knuth Shuffle. Ini berjalan dalam waktu O (n) dan mengocok di tempat, jadi lebih baik melakukan daripada teknik 'urutkan secara acak', meskipun lebih banyak baris kode. Lihat di sini untuk beberapa pengukuran kinerja komparatif. Saya telah menggunakan System.Random, yang bagus untuk keperluan non-kriptografi. *

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

Pemakaian:

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

* Untuk array yang lebih panjang, agar jumlah permutasi (sangat besar) sama-sama memungkinkan, perlu untuk menjalankan generator nomor acak semu (PRNG) melalui banyak iterasi untuk setiap swap untuk menghasilkan cukup entropi. Untuk array 500 elemen, hanya sebagian kecil dari kemungkinan 500! permutasi akan dimungkinkan untuk diperoleh menggunakan PRNG. Namun demikian, algoritma Fisher-Yates tidak bias dan oleh karena itu shuffle akan sebagus RNG yang Anda gunakan.

Anda sedang mencari algoritma pengocokan, bukan?

Oke, ada dua cara untuk melakukan ini: orang yang pandai-tetapi-orang-selalu-tampaknya-salah paham-itu-dan-salah-jadi-mungkin-tidak-sepintar-pandai cara, dan cara bodoh-seperti-batu-tapi-siapa-peduli-karena-itu-bekerja.

Cara bodoh

• Buat duplikat dari array pertama Anda, tetapi tandai setiap string dengan angka acak.
• Urutkan array duplikat sehubungan dengan nomor acak.

Algoritma ini berfungsi dengan baik, tetapi pastikan generator angka acak Anda tidak akan menandai dua string dengan nomor yang sama. Karena yang disebut Paradox Ulang Tahun , ini terjadi lebih sering daripada yang Anda harapkan. Kompleksitas waktunya adalah O ( n log n ).

Cara cerdik

Saya akan menggambarkan ini sebagai algoritma rekursif:

Untuk mengocok array ukuran n (indeks dalam kisaran [0 .. n -1]):

jika n = 0

• tidak melakukan apapun

jika n > 0

• (langkah rekursif) mengocok elemen n -1 pertama dari array
• pilih indeks acak, x , dalam kisaran [0 .. n -1]
• menukar elemen pada indeks n -1 dengan elemen pada indeks x

Setara iteratif adalah berjalan iterator melalui array, bertukar dengan elemen acak saat Anda pergi bersama, tetapi perhatikan bahwa Anda tidak dapat bertukar dengan elemen setelah yang iterator tunjuk. Ini adalah kesalahan yang sangat umum, dan mengarah pada shuffle yang bias.

Kompleksitas waktu adalah O ( n ).

Algoritma ini sederhana tetapi tidak efisien, O (N ² ). Semua "urutan oleh" algoritma biasanya O (N log N). Ini mungkin tidak membuat perbedaan di bawah ratusan ribu elemen tetapi akan untuk daftar besar.

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

Alasan mengapa O (N ² ) halus: List.RemoveAt () adalah operasi O (N) kecuali Anda menghapus secara berurutan dari akhir.

Anda juga dapat membuat metode ekstensi dari Matt Howells. Contoh.

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

Maka Anda bisa menggunakannya seperti:

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

Mengacak array adalah intensif karena Anda harus menggeser banyak string. Mengapa tidak hanya membaca secara acak dari array? Dalam kasus terburuk Anda bahkan bisa membuat kelas pembungkus dengan getNextString (). Jika Anda benar-benar perlu membuat array acak maka Anda bisa melakukan sesuatu seperti

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

* 5 adalah arbitrer.

Hanya dengan memikirkan dari atas kepala saya, Anda dapat melakukan ini:

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

Buat array float acak atau int dengan panjang yang sama. Urutkan array itu, dan lakukan swap yang sesuai pada array target Anda.

Ini menghasilkan jenis yang benar-benar independen.

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

Jacco, solusi Anda adalah IComparer khusus tidak aman. Sortir rutin memerlukan pembanding agar sesuai dengan beberapa persyaratan agar berfungsi dengan baik. Pertama di antara mereka adalah konsistensi. Jika pembanding dipanggil pada pasangan objek yang sama, ia harus selalu mengembalikan hasil yang sama. (perbandingannya juga harus transitif).

Kegagalan untuk memenuhi persyaratan ini dapat menyebabkan sejumlah masalah dalam penyortiran rutin termasuk kemungkinan loop tak terbatas.

Mengenai solusi yang mengaitkan nilai numerik acak dengan setiap entri dan kemudian mengurutkan berdasarkan nilai itu, ini mengarah ke bias yang melekat dalam output karena setiap kali dua entri diberi nilai numerik yang sama, keacakan output akan dikompromikan. (Dalam semacam rutin "stabil", mana yang pertama kali dalam input akan menjadi yang pertama di output. Array.Sort tidak kebetulan stabil, tetapi masih ada bias berdasarkan partisi yang dilakukan oleh algoritma Quicksort).

Anda perlu memikirkan tentang tingkat keacakan yang Anda butuhkan. Jika Anda menjalankan situs poker tempat Anda membutuhkan level acak kriptografi untuk melindungi dari penyerang yang teguh, Anda memiliki persyaratan yang sangat berbeda dari seseorang yang hanya ingin mengacak daftar lagu.

Untuk pengacakan daftar lagu, tidak ada masalah menggunakan PRNG yang diunggulkan (seperti System.Random). Untuk situs poker, itu bahkan bukan pilihan dan Anda perlu memikirkan masalah jauh lebih sulit daripada yang akan dilakukan siapa pun di stackoverflow. (menggunakan RNG kriptografi hanya permulaan, Anda perlu memastikan bahwa algoritme Anda tidak menimbulkan bias, bahwa Anda memiliki sumber entropi yang memadai, dan bahwa Anda tidak memaparkan keadaan internal yang akan membahayakan keacakan berikutnya).

Posting ini sudah dijawab dengan cukup baik - gunakan implementasi Durstenfeld dari shuffle Fisher-Yates untuk hasil yang cepat dan tidak bias. Bahkan ada beberapa implementasi yang diposting, meskipun saya perhatikan beberapa sebenarnya salah.

Saya menulis beberapa posting beberapa waktu lalu tentang menerapkan shuffles penuh dan parsial menggunakan teknik ini , dan (tautan kedua ini adalah tempat saya berharap untuk menambah nilai) juga posting lanjutan tentang bagaimana memeriksa apakah implementasi Anda tidak bias , yang dapat digunakan untuk memeriksa algoritma pengocokan. Anda dapat melihat di akhir posting kedua efek dari kesalahan sederhana dalam pemilihan angka acak dapat membuat.

Ok, ini jelas merupakan kesalahan besar dari pihak saya (meminta maaf ...), tetapi saya sering menggunakan metode yang cukup umum dan kuat secara kriptografis.

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 () adalah ekstensi pada setiap IEnumerable sehingga mendapatkan, katakanlah, angka dari 0 hingga 1000 secara acak dalam daftar dapat dilakukan dengan

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

Metode ini juga tidak akan memberikan kejutan ketika datang ke pengurutan, karena nilai pengurutan dihasilkan dan diingat tepat sekali per elemen dalam urutan.

Anda tidak perlu algoritma yang rumit.

Hanya satu baris sederhana:

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

Perhatikan bahwa kita perlu mengonversi Array ke yang Listpertama, jika Anda tidak menggunakannya Listdi tempat pertama.

Juga, ingatlah bahwa ini tidak efisien untuk array yang sangat besar! Kalau tidak bersih & sederhana.

Ini adalah solusi Konsol yang berfungsi lengkap berdasarkan contoh yang disediakan di sini :

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

Berikut cara sederhana menggunakan 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;
}