طريقة فعالة لإضفاء الطابع العشوائي على صفيف - رمز خلط ورق اللعب

Question

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

س: اكتب بنية بيانات فعالة لتنفيذ خلط ورق اللعب في جهاز iPod. يجب أن تعزف جميع الأغاني ، في كل مرة في ترتيب عشوائي مختلف ، لا ينبغي تكرار نفس الأغنية. (معظمها يا (ن))

أحد الحلول ، فكرت بعد المقابلة: يمكنني القيام بعمل سريع عشوائي دون عودة. حيث نختار بشكل عشوائي 1 محور O (1) ثم نفعل Quicksort O (N). الآن سيتم فرز الأغاني في ترتيب ما وألعبها حتى النهاية. بمجرد وصوله إلى النهاية ، سأختار مرة أخرى محورًا عشوائيًا ، وكرر هذه العملية مرارًا وتكرارًا.

التحيات ، سيثو

Answer 1

ضع جميع الأغاني في صفيف ... لكل عنصر في صفيف مبادلة مع وضع عشوائي.

Answer 2

تريد فيشر ييتس خلط. كن على دراية بأخطاء التنفيذ المذكورة في تلك الصفحة ، حيث إن الإجابة المقبولة حاليًا تقع على ما يرام.

Answer 3

حسنًا ، أول حل خطي ينبع إلى الذهن:

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

إدراج لكل O (n) + إزالة لكل O (n) + إدراج ثانية O (n). هذا من شأنه أن يؤدي بشكل عام إلى حل الوقت الخطي.

يحرر: لقد نسيت تمامًا المشي في القائمة. لذا ، بدلاً من ذلك ، يمكنك جعل النتيجة صفيفًا ثابتًا. قم ببث رأس القائمة المرتبطة ، وقم بتعيينه الفهرس العشوائي ، وقم بتعبئة الصفيف.

Answer 4

خوارزميات Nate (تحرير) وبرايان هما Fisher -yates خلط O (n) ، في حين أن الخلط عن طريق الفرز هو O (nlogn) ، ولكن قد يكون في الواقع أسرع في الممارسة (http://en.wikipedia.org/wiki/fisher٪ E2 ٪ 80 ٪ 93yates_shuffle#comparison_with_other_shuffling_algorithms). قد يكون لخطأ الأغاني عواقب غير مهمة ، ولكن إذا كنت تكتب خوارزمية خلط للعبة البوكر عبر الإنترنت ، فتأكد من أنك تعرف ما تفعله (http://www.cigital.com/news/index.php؟pg= الفن والفيروس = 20).

Answer 5

أنا مبتدئ ، اسمحوا لي أن أقول حلاً يذهل إلى الذهن ، إذا كان هناك أي شيء خاطئ ، فيرجى جعلني أعرف.

لنفترض أن الأغاني يتم تخزينها في قائمة منفردة أو مرتبطة بشكل مضاعف. في كل مرة يتم فيها فتح مشغل الموسيقى ، اختر رقمًا عشوائيًا أقل من (أي رقم تريده) تفترض K ، وعكس كل عقد K في القائمة ، بالمثل ، قم بذلك مرتين أو في Max Thrice (كما تريد) الذي سيستغرق O ( 2n) أو o (3n) الوقت لخلل. أخيرًا ، لديك مؤشر إلى العقدة الأخيرة من القائمة. وفي كل مرة يتم فيها الاستماع إلى أغنية (يتم زيارة العقدة) قم بإزالة العقدة وإدخالها بجوار العقدة الأخيرة التي يمكن القيام بها في وقت O (1). يستمر هذا حتى يتم إغلاق مشغل الموسيقى.

شكرا ، حريصة على معرفة صحة الجواب.

Answer 6

ما تريده هو فيشر ييتس خلط. إليك تطبيق في Java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

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