الجيل فرعية عشوائية وفريدة من نوعها

Question

ودعونا نقول لدينا أعداد 1-25 وعلينا أن نختار مجموعة من 15 أرقام.

ومجموعات الممكنة، إذا أنا الحق 3268760.

ومن هذه الخيارات 3268760، لديك لتوليد القول 100000

وماذا سيكون أفضل وسيلة لتوليد 100000 فريدة من نوعها وعشوائية من أن مجموعات فرعية؟

هل هناك طريقة، خوارزمية للقيام بذلك؟

إذا لم يكن كذلك، ما من شأنه أن يكون أفضل خيار للكشف عن التكرارات؟

وأنا أخطط للقيام بذلك في PHP ولكن من شأنه أن حل عام يكون كافيا، وأية إشارة لا إلى الكثير من "الأكاديمية" (أكثر واقعية) سوف يساعدني كثيرا.

Answer 1

وهنا حل في PHP على أساس الإجابة MJV، والذي هو كيف كنت أفكر في ذلك. إذا قمت بتشغيل ذلك لكامل 100K مجموعات، لم نرى في الواقع الكثير من الاصطدامات. ومع ذلك، وأنا من الصعب أن وضع نظام لتفاديها. بدلا من ذلك، نحن فقط التحقق منها بسرعة إلى حد ما.

وسأفكر حلول أفضل ... على هذا الكمبيوتر المحمول، يمكنني القيام به 10K مجموعات في 5 ثواني، 20K مجموعات في أقل من 20 ثانية. 100K يستغرق عدة دقائق.

ويتم تمثيل مجموعات كما [إينتس] (32-بت).

<?PHP
    /* (c) 2009 tim - anyone who finds a use for this is very welcome to use it with no restrictions unless they're making a weapon */

    //how many sets shall we generate?
    $gNumSets = 1000;

    //keep track of collisions, just for fun.
    $gCollisions = 0;

    $starttime = time();

    /**
     * Generate and return an integer with exactly 15 of the lower 25 bits set (1) and the other 10 unset (0)
     */ 
    function genSetHash(){
      $hash = pow(2,25)-1;

      $used = array();

      for($i=0;$i<10;){

        //pick a bit to turn off
        $bit = rand(0,24);

        if (! in_array($bit,$used)){
          $hash =  ( $hash & ~pow(2,$bit) );
          $i++;  
          $used[] = $bit;  
        }
      }
      return  $hash;
    }

    //we store our solution hashes in here.  
    $solutions = array();

    //generate a bunch of solutions.
    for($i=0;$i<$gNumSets;){
      $hash = genSetHash(); 

      //ensure no collisions
      if (! in_array($hash,$solutions)){
        $solutions[] = $hash;
        //brag a little.
        echo("Generated $i random sets in " . (time()-$starttime) . " seconds.\n");
        $i++;
      }else { 
        //there was a collision. There will generally be more the longer the process runs.
        echo "thud.\n"; 
        $gCollisions++;
      }
    }

    // okay, we're done with the hard work.  $solutions contains a bunch of
    // unique, random, ints in the right range.  Everything from here on out
    // is just output.

    //takes an integer with 25 significant digits, and returns an array of 15 numbers between 1 and 25
    function hash2set($hash){
      $set = array();
      for($i=0;$i<24;$i++){  
        if ($hash & pow(2,$i)){
          $set[] = $i+1;
        }
      }
      return $set;
    }

    //pretty-print our sets.
    function formatSet($set){
      return "[ " . implode(',',$set) . ']';
    }

    //if we wanted to print them, 
    foreach($solutions as $hash){
      echo formatSet(hash2set($hash)) . "\n";
    }

    echo("Generated $gNumSets unique random sets in " . (time()-$starttime) . " seconds.\n");

    echo "\n\nDone.  $gCollisions collisions.\n";

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

Answer 2

وهناك طريقة لتوليد عينة من مجموعات فرعية وهذا هو عشوائي، مضمونة ليس لديهم مكررة، يستخدم O (1) تخزين، ويمكن إعادة لدت في أي وقت. أولا، كتابة دالة ل توليد مزيج نظرا لمعجمية مؤشر . ثانيا، استخدام التقليب المزيف من الأعداد الصحيحة لخطوة من خلال تلك المجموعات في ترتيب عشوائي تنافسية الأول (ن، م). ببساطة إطعام الأرقام من 0 ... 100000 في التقليب، استخدم إخراج التقليب كمدخل لمولد الجمع، ومعالجة مجموعة الناتجة عن ذلك.

Answer 3

هل لديهم لتكون عشوائية حقا؟ أو على ما يبدو عشوائيا؟

والاختيار: توليد مجموعة مع كل 25 - "خلط" 15 العناصر الأولى باستخدام فيشر ييتس / خلط كانوث، ومن ثم الاختيار إذا كنت قد رأيت أن التقليب من العناصر ال 15 الأولى من قبل. إذا كان الأمر كذلك، والاستخفاف، وإعادة المحاولة.

والتكرارات: لديك 25 القيم الموجودة هناك أم لا - وهذا يمكن تجزئته بشكل مسلي إلى قيمة عدد صحيح (إذا كان العنصر 1ST موجودا، إضافة 2 ^ 0، إذا كان الثاني هو، إضافة 2 ^ 1، وما إلى ذلك - يمكن أن تكون ممثلة مباشرة إلى عدد 25 بت)، حتى تتمكن من التحقق بسهولة إذا كنت قد رأيت بالفعل.

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

Answer 4

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

ونظرا لهذا RNG يمكنك "رسم" 10 (أو 15، وقراءة أدناه) أرقام بين 1 و 25. وهذا قد يتطلب التي قمت مضاعفة (وجولة) الرقم العشوائي التي تنتجها المولدات، وأنك تجاهل الأرقام التي فوق 25 (أي رسم مرة أخرى)، اعتمادا على API المحدد المرتبطة RNG، ولكن مرة أخرى الحصول على رسم في نطاق معين تافهة. سوف تحتاج أيضا إلى إعادة رسم عندما يأتي عدد من جديد.

وأقترح عليك أن تحصل على 10 أرقام فقط، وهذه يمكن إزالتها من التسلسل الكامل 1-25 لإنتاج مجموعة من 15. وبعبارة أخرى رسم 15 لوضع هو نفس الرسم 10 لإخراج ...

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

في هذا مسألة تفرد 100000 مجموعات أخرجت من جميع مجموعات الممكنة، واحتمال حدوث تصادم يبدو منخفضا نسبيا. تحرير: عفوا ... لقد كنت متفائلا ... وهذا احتمال ليس منخفضا جدا، مع حوالي 1.5٪ فرصة حدوث تصادم تبدأ بعد رسم 50000، وسوف يكون هناك عدد غير قليل من التصادم، وهو ما يكفي لتبرير نظام لاقصائهم ...