генерация случайных и уникальных подмножеств

Question

Допустим, у нас есть числа от 1 до 25, и мы должны выбрать наборы из 15 чисел.

Возможные наборы, если я прав, 3268760.

Из этих 3268760 опций вы должны сгенерировать, скажем, 100000

Как лучше всего создать 100000 уникальных и случайных из этих подмножеств?

Есть ли способ, алгоритм для этого?

Если нет, что будет лучшим вариантом для обнаружения дубликатов?

Я планирую сделать это на PHP, но общего решения будет достаточно, и любая ссылка не на «академический» (более практичный) мне очень поможет.

Answer 1

Существует способ генерировать выборку подмножеств, которая является случайной, гарантированно не имеет дубликатов, использует хранилище O (1) и может быть сгенерирована заново в любое время. Сначала напишите функцию для , сгенерирующую комбинацию с учетом лексического индекса . Во-вторых, используйте псевдослучайную перестановку первых Combin (n, m) целых чисел , чтобы пройти через эти комбинации в случайном порядке. Просто введите числа 0 ... 100000 в перестановку, используйте выходные данные перестановки в качестве входных данных для генератора комбинации и обработайте полученную комбинацию.

Answer 2

Вот решение в PHP, основанное на ответе mjv, как я об этом думал. Если вы запускаете его для полных 100 тыс. Наборов, вы действительно видите много коллизий. Тем не менее, мне трудно разработать систему, чтобы избежать их. Вместо этого мы просто проверяем их довольно быстро.

Я подумаю о лучших решениях ... на этом ноутбуке я могу сделать 10 тысяч подходов за 5 секунд, 20 тысяч наборов менее чем за 20 секунд. 100 КБ занимает несколько минут.

Наборы представлены в виде (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 3

Генератор случайных чисел (ГСЧ) вашей среды предоставит вам случайные числа, которые равномерно распределены в определенном диапазоне. Этот тип распределения часто необходим, например, если ваше подмножество имитирует лотерейные рисунки, но важно упомянуть этот факт, если вы моделируете, скажем, возраст людей, найденных на основании средней школы ...

Учитывая этот ГСЧ, вы можете «нарисовать» 10 (или 15, см. Ниже) чисел от 1 до 25. Для этого может потребоваться умножить (и округлить) случайное число, полученное генератором, и игнорировать числа, которые являются выше 25 (т.е. отрисовка снова), в зависимости от точного API, связанного с ГСЧ, но опять же получение чертежа в заданном диапазоне является тривиальным. Вам также нужно будет перерисовать, когда число снова появится.

Я предлагаю вам получить только 10 чисел, поскольку их можно удалить из полной последовательности 1-25, чтобы получить набор 15. Другими словами, рисунок 15, который нужно вставить, - это тот же рисунок 10, который нужно вынуть ...

Далее вам необходимо подтвердить уникальность наборов. Вместо того, чтобы хранить весь набор, вы можете использовать хеш для уникальной идентификации каждого набора. Это должно занимать менее 25 бит, поэтому может храниться в 32-битном целом числе. Затем вам необходимо иметь эффективное хранилище для 100 000 из этих значений; если вы не хотите сохранить это в базе данных.

В этом вопросе об уникальности 100 000 наборов из всех возможных наборов вероятность столкновения кажется относительно низкой. Редактировать: Упс ... Я был оптимистичен ... Эта вероятность не так мала, с вероятностью около 1,5% столкновения, начавшегося после рисования 50 000-го, будет довольно много коллизий, достаточных для того, чтобы система исключила их ...

Answer 4

Должны ли они быть действительно случайными? Или, казалось бы, случайно?

Выбор: сгенерируйте набор со всеми 25 - «перемешайте» первые 15 элементов, используя Fisher-Yates / Knuth shuffle, а затем проверьте, видели ли вы эту перестановку первых 15 элементов ранее. Если это так, не обращайте внимания и повторите попытку.

Дубликаты: у вас есть 25 значений, которые есть или нет - это может быть тривиально хешировано до целочисленного значения (если присутствует 1-й элемент, добавьте 2 ^ 0, если второй - добавьте 2 ^ 1 и т. Д. он может быть непосредственно представлен как 25-битное число), поэтому вы можете легко проверить, видели ли вы его уже.

Вы получите немало коллизий, но если это не фрагмент критичной производительности, это может быть выполнимо.