aleatória e subconjuntos únicos geração

Question

Vamos dizer que temos números de 1 a 25 e temos de escolher séries de 15 números.

As possíveis conjuntos são, se eu estou certo 3.268.760.

Desses 3268760 opções, você tem que gerar dizer 100000

Qual seria a melhor maneira de gerar 100000 única e aleatória de que os subconjuntos?

Existe uma maneira, um algoritmo para fazer isso?

Se não, qual seria a melhor opção para detectar duplicatas?

Eu estou planejando fazer isso em PHP, mas uma solução geral seria suficiente, e qualquer referência não muito 'acadêmico' (mais prático) iria me ajudar muito.

Answer 1

Aqui está uma solução em PHP com base na resposta das mjv, que é como eu estava pensando sobre isso. Se você executá-lo para um total de 100 mil conjuntos, você realmente ver um monte de colisões. No entanto, estou dificuldade em conceber um sistema para evitá-los. Em vez disso, nós apenas vê-los rapidamente.

Vou pensar sobre as melhores soluções ... sobre este laptop, eu posso fazer 10k conjuntos em 5 segundos, 20k conjuntos em menos de 20 segundos. 100k demora vários minutos.

Os sets são representados como ints (32 bits).

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

Eu acho que está tudo correto, mas é tarde, e eu tenho vindo a desfrutar de vários muito bons garrafas de cerveja.

Answer 2

Existe um modo para gerar uma amostra dos subconjuntos que é aleatória, garantidos não têm duplicados, utiliza ó (1) de armazenagem, e pode ser re-gerado a qualquer momento. Em primeiro lugar, escrever uma função para gerar uma combinação dada a sua lexical índice . Em segundo lugar, usar um pseudo-aleatório permutação do primeiro Combin (n, m) números inteiros a passo através aquelas combinações em uma ordem aleatória. Basta alimentar os números 0 ... 100000 para a permutação, utilizar a saída do permutação como entrada para o gerador de combinação, e processar a combinação resultante.

Answer 3

Será que eles têm de ser verdadeiramente aleatório? Ou aparentemente aleatório?

Seleção: gerar um conjunto com todos os 25 - "embaralhar" os primeiros 15 elementos usando Fisher-Yates / shuffle Knuth, e em seguida, verifique se você viu que permutação dos primeiros 15 elementos antes. Se assim for, desrespeito, e tente novamente.

Duplicatas: Você tem 25 valores que estão lá ou não - isso pode ser trivialmente hash para um valor inteiro (se o 1º elemento está presente, adicione 2 ^ 0, se o segundo é, adicione 2 ^ 1, etc. - ele pode ser directamente representados como um número de 25 bits), assim você pode facilmente verificar se você já viu isso já.

Você vai ter um pouco de colisões, mas se não está um trecho crítico de desempenho, pode ser factível.

Answer 4

O gerador de números aleatórios (RNG) do seu ambiente irá fornecer-lhe números aleatórios que são uniformemente distribuídos em um determinado intervalo. Este tipo de distribuição é muitas vezes o que é necessário, dizer se o seu subconjunto simulados sorteios, mas é importante mencionar esse fato no caso do seu está modelando dizer a idade das pessoas encontradas em razão de uma escola média ...

Dada esta RNG você pode "desenhar" 10 (ou 15, leia abaixo) números entre 1 e 25. Isso pode exigir que você multiplicar (e volta) o número aleatório produzida pelo gerador, e que você ignora números que são acima de 25 (ou seja, desenhar de novo), dependendo do API exacta associada com o RNG, mas novamente a obtenção de um desenho em um determinado intervalo é trivial. Você também vai precisar de re-desenhar quando um número surge novamente.

Eu sugiro que você começa 10 números apenas, como estas podem ser removidas da seqüência completa 1-25 para produzir um conjunto de 15. Em outras palavras desenho 15 a colocou no é o mesmo desenho 10 para tirar ...

Em seguida, você precisa para afirmar a singularidade dos sets. Em vez de armazenar todo o conjunto, você pode usar um hash para identificar cada conjunto de forma exclusiva. Isto deve demorar menos que 25 bits, de modo que pode ser armazenada em um número inteiro de 32 bits. Você, então, precisa ter um armazenamento eficiente para até 100.000 destes valores; a menos que você deseja armazenar isso em um banco de dados.

Nesta questão da singularidade de 100.000 conjuntos retirados de todos os conjuntos possíveis, a probabilidade de uma colisão parece relativamente baixo. Edit: Oops ... I foi otimista ... Essa probabilidade não é tão baixa, com cerca de 1,5% de chance de uma colisão começando depois de desenhar a 50000, haverá algumas colisões, o suficiente para justificar um sistema de excluí-los ...