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

Question

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

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

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

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

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

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

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

Answer 1

Вот решение в 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 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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