أفضل طريقة عشوائية صفيف .صافي

Question

ما هي أفضل طريقة عشوائية مجموعة من السلاسل مع .الشبكة ؟ بلدي مجموعة تحتوي على حوالي 500 سلاسل أود أن خلق جديد Array مع نفس السلاسل ولكن في ترتيب عشوائي.

يرجى إدراج C# على سبيل المثال في الجواب.

Answer 1

إذا كنت على .NET framework 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()

تحرير الثاني ، ردا على تصريحات هذا النظام.عشوائية "ليس threadsafe" و "مناسبة فقط لعبة التطبيقات" بسبب عودته على التسلسل:كما تستخدم في بلدي على سبيل المثال ، Random() هو تماما مؤشر الترابط-الآمن ، إلا إذا كنت السماح الروتينية التي عشوائية مجموعة إلى إعادة إدخالها في هذه الحالة سوف تحتاج إلى شيء مثل lock (MyRandomArray) على كل حال لكي لا الفاسدة البيانات الخاصة بك ، التي من شأنها حماية rnd وكذلك.

كما أنه ينبغي أن يفهم جيدا أن هذا النظام.عشوائية كمصدر الكون ليست قوية جدا.كما لوحظ في وثائق 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]);
    }

Answer 2

التنفيذ التالية يستخدم خوارزمية فيشر ييتس الملقب 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

* أطول المصفوفات ، من أجل جعل (كبيرة جدا) عدد التباديل المحتملة على حد سواء سيكون من الضروري تشغيل الزائفة مولد رقم عشوائي (اللوائح) من خلال العديد من التكرارات لكل مبادلة لإنتاج ما يكفي من الكون.عن 500 عنصر صفيف سوى جزء صغير جدا من الممكن 500!التباديل سوف يكون من الممكن الحصول على استخدام اللوائح.ومع ذلك ، فإن خوارزمية فيشر ييتس هو غير منحازة وبالتالي المراوغة سوف تكون جيدة كما RNG تستخدمها.

Answer 3

كنت تبحث عن خلط خوارزمية, صحيح ؟

حسنا, هناك طريقتان للقيام بذلك:على clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-كل طريقة و البكم-كما-الصخور-ولكن-من-العطاء-لأن ذلك يعمل الطريقة.

طريقة غبية

• إنشاء نسخة مكررة من أول مجموعة ، ولكن الوسم كل سلسلة مع عدد عشوائي.
• نوع مكررة مجموعة فيما يتعلق رقم عشوائي.

هذه الخوارزمية تعمل بشكل جيد, ولكن تأكد من أن جهاز مولد رقم عشوائي من غير المرجح أن الوسم سلسلتين مع نفس العدد.بسبب ما يسمى عيد ميلاد مفارقة, هذا يحدث في كثير من الأحيان مما قد تتوقع.وقتها تعقيد O(n سجل n).

طريقة ذكية

أنا أصف هذا كما العودية الخوارزمية:

لخلط مجموعة من حجم n (المؤشرات في نطاق [0..n-1]):

إذا n = 0

• لا تفعل شيئا

إذا n > 0

• (العودية خطوة) خلط الأولى n-1 عناصر المصفوفة
• اختيار عشوائي المؤشر ، x, في مجموعة [0..n-1]
• مبادلة عنصر في المؤشر n-1 مع عنصر في المؤشر x

تكرارية أي ما يعادل المشي مكرر من خلال مجموعة مبادلة مع العناصر العشوائية كما تذهب على طول ، ولكن لاحظ أنه لا يمكنك مبادلة مع عنصر بعد واحد مكرر نقاط.هذا خطأ شائع جدا, و يؤدي إلى منحازة المراوغة.

الوقت تعقيد O(n).

Answer 4

هذه الخوارزمية بسيطة ولكن ليست فعالة ، 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²) خفية: قائمة.RemoveAt() هي O(N) عملية إلا إذا قمت بإزالة في أمر من النهاية.

Answer 5

يمكنك أيضا جعل ارشادية طريقة للخروج من مات هاولز.على سبيل المثال.

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

Answer 6

العشوائي مجموعة مكثفة كما كنت قد تحول حول مجموعة من السلاسل.لماذا لا مجرد عشوائيا قراءة من المصفوفة ؟ في أسوأ الأحوال يمكنك حتى إنشاء المجمع الدرجة مع getNextString().إذا كنت حقا لا تحتاج إلى إنشاء مجموعة عشوائية ثم هل يمكن أن تفعل شيئا مثل

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

*في 5 تعسفي.

Answer 7

مجرد التفكير من على قمة رأسي ، هل يمكن أن تفعل هذا:

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

Answer 8

توليد مجموعة عشوائية من العوامات أو رجات من نفس الطول.نوع المصفوفة و هل المقابلة مقايضة على الهدف الخاص بك مجموعة.

هذا ينتج حقا مستقلة نوعا ما.

Answer 9

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

Answer 10

Jacco ، الحل إيسينج مخصص IComparer ليست آمنة.نوع الروتينية تتطلب comparer لتتوافق مع العديد من المتطلبات لكي يعمل بشكل صحيح.أول بينها هو الاتساق.إذا كان comparer على نفس زوج من الكائنات ، فإنه يجب العودة دائما نفس النتيجة.(المقارنة يجب أيضا أن تكون متعدية).

عدم تلبية هذه المتطلبات يمكن أن يسبب أي عدد من المشاكل في الفرز الروتينية بما في ذلك إمكانية حلقة لا نهائية.

بشأن الحلول التي ربط عشوائي قيمة رقمية مع كل دخول ومن ثم فرز قبل أن قيمة هذه يؤدي إلى تحيز في الإخراج بسبب أي وقت من اثنين إدخالات يتم تعيين نفس قيمة رقمية عشوائية سوف يكون الإخراج للخطر.(في حالة "مستقرة" نوع من الروتين ، أيهما الأولى في المدخلات سوف تكون الأولى في الإخراج.الصفيف.نوع لا يحدث أن تكون مستقرة, ولكن لا يزال هناك تحيز على أساس التقسيم الذي قامت به فرز سريع الخوارزمية).

تحتاج إلى القيام ببعض التفكير في أي مستوى من العشوائية التي تحتاجها.إذا كنت تقوم بتشغيل موقع لعبة البوكر حيث كنت في حاجة التشفير مستويات من العشوائية إلى حماية ضد مهاجم العزم لديك متطلبات مختلفة جدا من شخص يريد فقط بطريقة عشوائية أغنية قائمة التشغيل.

عن أغنية قائمة-خلط لا يوجد مشكلة في استخدام المصنف PRNG (مثل نظام.عشوائي).عن موقع لعبة البوكر ، ليس خيارا بل و تحتاج إلى التفكير في مشكلة أصعب من أي شخص سيفعل لك على ستاكوفيرفلوو.(باستخدام التشفير RNG هي البداية فقط, كنت بحاجة للتأكد من أن خوارزمية الخاص بك لا يعرض التحيز أن لديك ما يكفي من مصادر الكون و التي لا تعرض أي الدولة الداخلي من شأنه أن يعرض للخطر اللاحقة العشوائية).

Answer 11

هذا المنصب بالفعل بشكل جيد أجاب - استخدام Durstenfeld تنفيذ فيشر ييتس خلط سريع و غير منحازة النتيجة.بل كانت هناك بعض التطبيقات نشرها ، على الرغم من أنني ملاحظة بعض هي في الواقع غير صحيحة.

كتبت عدة مشاركات في حين يعود عن تنفيذ كامل و جزئي المراوغات باستخدام هذه التقنية, و (هذه الوصلة الثانية حيث آمل أن تضيف قيمة) أيضا وظيفة المتابعة حول كيفية التحقق من ما إذا كان التطبيق الخاص بك هو غير متحيزة, والتي يمكن استخدامها للتحقق من أي خلط الخوارزمية.يمكنك أن ترى في نهاية الوظيفة الثانية تأثير خطأ بسيط في رقم عشوائي اختيار يمكن أن تجعل.

Answer 12

حسنا, هذا هو واضح عثرة من جانبي (يعتذر...), ولكن أنا غالبا ما تستخدم تماما العامة و قوية مشفر الأسلوب.

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

خلط ورق اللعب() هو امتداد على أي IEnumerable حتى الحصول على, تقول الأرقام من 0 إلى 1000 في ترتيب عشوائي في قائمة يمكن القيام به مع

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

هذه الطريقة أيضا لن تعطي أي مفاجآت عندما يتعلق الأمر الفرز منذ النوع يتم إنشاء قيمة وتذكرت بالضبط مرة واحدة لكل عنصر في تسلسل.

Answer 13

أنت لا تحتاج إلى تعقيد الخوارزميات.

فقط خط واحد بسيط:

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

علما أننا بحاجة إلى تحويل Array إلى List أولا, إذا كنت لا تستخدم List في المقام الأول.

أيضا ، اعتبارنا أن هذه ليست فعالة على صفائف كبيرة!إلا انها نظيفة و بسيطة.

Answer 14

هذا هو استكمال وحدة العمل على أساس حل على سبيل المثال قدمت هنا:

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

Answer 15

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

Answer 16

هذا الرمز المراوغات الأرقام في صفيف.

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

Answer 17

هنا هو طريقة بسيطة باستخدام 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);

Answer 18

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