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

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

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

Наборы представлены как (32-битные) ints.

<?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"; 

Я думаю, что все правильно, но уже поздно, и я наслаждался несколькими очень хорошими бутылками пива.

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

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

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

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

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

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

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

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

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

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