it-swarm-eu.dev

Nejlepší způsob, jak náhodně uspořádat pole pomocí rozhraní .NET

Jaký je nejlepší způsob náhodného uspořádání řetězců řetězců .NET? Moje pole obsahuje asi 500 řetězců a rád bych vytvořil nový Array se stejnými řetězci, ale v náhodném pořadí.

V odpovědi uveďte příklad C #.

118
Mats

Pokud jste na .NET 3.5, můžete použít následující IEnumerable coolness (VB.NET, ne C #, ale nápad by měl být jasný ...):

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

Upravit: OK a zde je odpovídající kód VB.NET:

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

Druhá úprava, v odezvě na poznámky, že System.Random "není vlákno" a "vhodné pouze pro aplikace pro hračky" v důsledku navrácení časové posloupnosti: jak je uvedeno v mém příkladu, Random () je dokonale bezpečný pro vlákna, pokud dovoluje vám rutinu, ve které náhodně nastavíte pole, které má být znovu zadáno, v takovém případě budete potřebovat něco jako lock (MyRandomArray) tak, abyste nepoškodili svá data, která budou také chránit rnd

Také by mělo být dobře známo, že System.Random jako zdroj entropie není moc silný. Jak je uvedeno v dokumentaci MSDN , měli byste použít něco, co je odvozeno od System.Security.Cryptography.RandomNumberGenerator, pokud děláte cokoliv. Například:

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

Následující implementace používá Fisher-Yates algoritmus . To běží v O(n) čas a shuffle v místě, tak je lépe vykonávat než 'třídit náhodně' technika, ačkoli to je více řádků kódu. Viz zde pro některá srovnávací měření výkonu. Použil jsem System.Random, což je v pořádku pro nekryptografické účely. *

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

Používání:

var array = new int[] {1, 2, 3, 4};
new Random().Shuffle(array);

Pro delší pole, aby dělal (extrémně velký) počet permutations stejně pravděpodobný to by bylo nutné provozovat pseudo-náhodné číslo generátor (PRNG) přes mnoho iterací pro každou výměnu produkovat dost entropie. Pro 500-elementové pole jen velmi malý zlomek možných 500! permutací bude možné získat pomocí PRNG. Algoritmus Fisher-Yates je však nezkreslený, a proto bude shuffle stejně dobrý jako RNG, který používáte.

181
Matt Howells

Hledáte algoritmus shufflingu, že?

Okay, existují dva způsoby, jak toho dosáhnout: chytrý-ale-lidé-vždy-zdát-k-misunderstand-it-a-get-it-špatný-tak-možná-jeho-ne-to-to-chytrý-po-všichni způsobem, a dumb-as-skály-ale-kdo-cares-protože-to-funguje způsobem.

Hloupá cesta

  • Vytvořte duplikát prvního pole, ale označte každý řetězec náhodným číslem.
  • Seřadit duplicitní pole s ohledem na náhodné číslo.

Tento algoritmus funguje dobře, ale ujistěte se, že generátor náhodných čísel nebude pravděpodobně označovat dva řetězce se stejným číslem. Kvůli tzv. Narozeninám Paradox , to se stává častěji, než byste čekali. Jeho časová složitost je O (n log n).

Chytrý způsob

Popíšu to jako rekurzivní algoritmus:

Chcete-li zamíchat pole velikosti n (indexy v rozsahu [0 ..n- 1]:

jestliže n = 0
  • nedělat nic
jestliže n> 0
  • (rekurzivní krok) zamíchat první n- 1 prvky pole
  • vyberte náhodný index, x, v rozsahu [0 ..n- 1]
  • vyměnit prvek v indexu n- 1 s prvkem v indexu x

Iterativní ekvivalent je procházet iterátorem přes pole, vyměňovat si s náhodnými prvky, zatímco vy jdete podél, ale všimnout si, že vy nemůžete swap s elementem po ten to iterator ukáže na. To je velmi častá chyba a vede k neobjektivnímu shuffle.

Časová složitost je O (n).

16
Pitarou

Tento algoritmus je jednoduchý, ale neúčinný, O (N2). Všechny algoritmy "pořadí podle" jsou typicky O (N log N). To pravděpodobně nedělá rozdíl pod stovkami tisíc prvků, ale pro velké seznamy.

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

Důvod, proč je to O (N2) je subtle: List.RemoveAt () je operace O(N), pokud neodstraníte v pořadí od konce.

8
Sklivvz

Můžete také použít metodu rozšíření z Matt Howells. Příklad.

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

Pak jej můžete použít jako: 

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

Náhodné uspořádání pole je intenzivní, protože se musíte pohybovat kolem svazku strun. Proč ne jen náhodně číst z pole? V nejhorším případě můžete dokonce vytvořit třídu wrapperu s getNextString (). Pokud opravdu potřebujete vytvořit náhodné pole, můžete něco udělat

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

* 5 je libovolné. 

1
stimms

Jen přemýšlíte nad hlavou, můžete to udělat:

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

Tento post už byl docela dobře zodpovězen - použijte Durstenfeldovu implementaci Fisher-Yates shuffle pro rychlý a nestranný výsledek. Dokonce byly implementovány některé implementace, i když některé poznámky jsou ve skutečnosti nesprávné.

Napsal jsem pár příspěvků o tom, co je { implementace úplných a částečných zamíchání pomocí této techniky , a (tento druhý odkaz je místo, kde doufám přidat hodnotu) také následný příspěvek o jak zkontrolovat, zda je vaše implementace nezkreslená , který lze použít ke kontrole jakéhokoliv algoritmu shuffle. Na konci druhého příspěvku můžete vidět efekt jednoduché chyby při výběru náhodných čísel.

1
Greg Beech

Generovat pole náhodných plováků nebo ints stejné délky. Řadit pole a odpovídající swapy na cílové pole.

To poskytuje skutečně nezávislý druh.

0
Nick
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);
}
0
nullDev

Jedná se o kompletní pracovní řešení založené na příklad uvedený zde :

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
usefulBee

Tento kód zamíchá čísla v poli.

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }
0
Bilal

Nepotřebujete složité algoritmy.

Jediná jednoduchá linka:

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

Nejprve je třeba převést soubor Array na List, pokud na prvním místě nepoužíváte List.

Také si uvědomte, že to není efektivní pro velmi velká pole! Jinak je to čisté a jednoduché.

0
bytecode77

Ok, tohle je zřetelně rána z mé strany (omlouvá se ...), ale často používám poměrně obecnou a kryptograficky silnou metodu.

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 () je rozšíření na libovolné IEnumerable, takže získávání, řekněme, čísla od 0 do 1000 v náhodném pořadí v seznamu lze provést pomocí

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

Tato metoda také nedává žádné překvapení, pokud jde o třídění, protože hodnota řazení je generována a zapamatována přesně jednou na prvek v sekvenci.

0
jlarsson

Jacco, vaše řešení je vlastní IComparer není bezpečné. Řádky řazení vyžadují, aby srovnávací zařízení vyhovovalo několika požadavkům, aby fungovalo správně. První z nich je konzistence. Pokud je komparátor volán na stejný pár objektů, musí vždy vrátit stejný výsledek. (srovnání musí být také tranzitivní).

Nesplnění těchto požadavků může způsobit řadu problémů v třídicí rutině včetně možnosti nekonečné smyčky. 

Pokud jde o řešení, která spojují náhodnou číselnou hodnotu s každou položkou a poté se třídí podle této hodnoty, vedou k inherentnímu vychýlení ve výstupu, protože kdykoli jsou dvě položky přiřazeny stejné číselné hodnoty, bude ohrožena náhodnost výstupu. (V "stabilní" třídě rutina, která je první na vstupu bude první ve výstupu. Array.Sort se nestane, že je stabilní, ale stále existuje zkreslení na základě rozdělení provedeného algoritmem Quicksort).

Musíte udělat nějaké přemýšlení o tom, jakou úroveň náhodnosti požadujete. Pokud provozujete pokerovou stránku, kde potřebujete kryptografickou úroveň náhodnosti, abyste mohli chránit před určeným útočníkem, máte velmi odlišné požadavky od někoho, kdo chce náhodně vybrat seznam skladeb.

Pro míchání seznamu skladeb není problém použít nasazený PRNG (například System.Random). Pro pokerovou stránku to není ani možnost a musíte o problému přemýšlet mnohem těžší než kdokoli jiný. (pomocí kryptografického RNG je jen začátek, musíte zajistit, aby váš algoritmus nezaváděl zkreslení, že máte dostatečné zdroje entropie, a že nevystavujete žádný vnitřní stav, který by ohrozil následnou náhodnost).

0
Andrew
        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();
0
Nitesh Katare