ما هي أفضل طريقة لترتيب ترتيب المصفوفة بطريقة عشوائية في PHP دون استخدام وظيفة shuffle()؟

Question

لقد سُئلت هذا السؤال في مقابلة عمل.لقد اختلفنا أنا والمحاور حول الإجابة الصحيحة.وأتساءل عما إذا كان أي شخص لديه أي بيانات حول هذا الموضوع.

تحديث:كان يجب أن أذكر أن استخدام shuffle() ممنوع منعا باتا ...آسف.

Answer 1

يمكنك استخدام خلط فيشر ييتس.

Answer 2

shuffle($arr);

:)

يحرر:يجب أن أوضح...إن تعريفي للأفضل لا يتضمن كفاءة الخوارزمية فحسب، بل يتضمن إمكانية قراءة التعليمات البرمجية وقابلية صيانتها أيضًا.إن استخدام وظائف المكتبة القياسية يعني الحفاظ على قدر أقل من التعليمات البرمجية وقراءة أقل بكثير أيضًا.أبعد من ذلك، يمكنك الدخول في مناقشات لمدة عام مع أساتذة الدكتوراه حول أفضل وظيفة "عشوائية حقيقية"، لذلك سيختلف معك دائمًا شخص ما بشأن أسئلة التوزيع العشوائي.

Answer 3

حسنًا، إليك الحل الذي توصلت إليه:

function randomize_array_1($array_to_randomize) {
    $new_array = array();
    while (count($array_to_randomize) > 0) {
        $rand_num = rand(0, count($array_to_randomize)-1);
        $extracted = array_splice($array_to_randomize, $rand_num, 1);
        $new_array[] = $extracted[0];
    }
    return $new_array;
}

وهذا هو الحل له:

function randomize_array_2($array_to_randomize) {
    usort($array_to_randomize, "rand_sort");
    return $array_to_randomize;
}
function rand_sort($a, $b) {
    return rand(-1, 1);
}

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

randomize_array_1:
    [2, 3, 1] => 166855
    [2, 1, 3] => 166692
    [1, 2, 3] => 166690
    [3, 1, 2] => 166396
    [3, 2, 1] => 166629
    [1, 3, 2] => 166738

randomize_array_2:
    [1, 3, 2] => 147781
    [3, 1, 2] => 73972
    [3, 2, 1] => 445004
    [1, 2, 3] => 259406
    [2, 3, 1] => 49222
    [2, 1, 3] => 24615

كما ترون، توفر الطريقة الأولى توزيعًا مثاليًا تقريبًا مما يشير إلى أنها عشوائية إلى حد ما، في حين أن الطريقة الثانية موجودة في كل مكان.

Answer 4

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

طريقة الخلط الخاطئة:

for (i is 1 to n) Swap i with random position between 1 and n

الطريقة الصحيحة للخلط:

for (i is 1 to n) Swap i with random position between i and n

قم برسم التوزيع الاحتمالي لهذه الحالات ومن السهل معرفة سبب عدم صحة الحل الأول.

Answer 5

الطريقة "الصحيحة" غامضة جدًا.أفضل (الأسرع / الأسهل / الأكثر أناقة) لفرز المصفوفة هو استخدام وظيفة shuffle() المضمنة فقط.

Answer 6

لدى PHP وظيفة مدمجة --> shuffle() .أود أن أقول إن هذا يجب أن يفعل ما تريد، ولكن من المرجح أن يكون أي شيء غير "عشوائي" تمامًا.

يفحص http://computer.howstuffworks.com/question697.htm للحصول على وصف بسيط عن سبب صعوبة الحصول على عشوائية كاملة من جهاز كمبيوتر.

Answer 7

اجابة قصيرة:PHP array_rand() وظيفة

نظرًا لأن استخدام وظيفة الخلط محظور، سأستخدمها $keys = array_rand($myArray, count($myArray)) لإرجاع مجموعة من المفاتيح من $myArray بترتيب عشوائي.من هناك يجب أن يكون من السهل إعادة تجميعها في مصفوفة جديدة تم اختيارها بشكل عشوائي.شيء مثل:

$keys = array_rand($myArray, count($myArray));
$newArray = array();

foreach ($keys as $key) {
$newArray[$key] = $myArray[$key];
}