Como gerar uma lista de n números aleatórios únicos em Ruby?

Question

Isto é o que eu tenho até agora:

myArray.map!{ rand(max) }

Obviamente, no entanto, às vezes os números na lista não são exclusivos. Como posso ter certeza que meu lista contém apenas números exclusivos sem ter que criar uma lista maior do que eu, em seguida, basta escolher as únicas n números?

Editar:
Eu realmente gostaria de ver este feito w / o loop -. Se possível

Answer 1

Isto usa Set:

require 'set'

def rand_n(n, max)
    randoms = Set.new
    loop do
        randoms << rand(max)
        return randoms.to_a if randoms.size >= n
    end
end

Answer 2

(0..50).to_a.sort{ rand() - 0.5 }[0..x] 

(0..50).to_a pode ser substituído por qualquer matriz. 0 é "minvalue", 50 é "valor máximo" x é "quantos valores que eu quero para fora"

é claro, a sua impossibilidade de x para ser autorizado a ser maior do que max-min:)

Em expansão de como isso funciona

(0..5).to_a  ==> [0,1,2,3,4,5]
[0,1,2,3,4,5].sort{ -1 }  ==>  [0, 1, 2, 4, 3, 5]  # constant
[0,1,2,3,4,5].sort{  1 }  ==>  [5, 3, 0, 4, 2, 1]  # constant
[0,1,2,3,4,5].sort{ rand() - 0.5 }   ==>  [1, 5, 0, 3, 4, 2 ]  # random
[1, 5, 0, 3, 4, 2 ][ 0..2 ]   ==>  [1, 5, 0 ]

Notas de rodapé:

É importante ressaltar que no momento esta questão foi originalmente respondeu, em setembro de 2008, que Array#shuffle foi ou não estão disponíveis ou não já conhecido para mim, daí a aproximação em Array#sort

E há uma enxurrada de edições sugeridas a esta como resultado.

Assim:

.sort{ rand() - 0.5 }

Pode ser melhor, e mais curto expressa em implementações moderna rubi usando

.shuffle

Além disso,

[0..x]

Pode ser mais, obviamente, escrito com Array#take como:

.take(x)

Assim, a maneira mais fácil de produzir uma sequência de números aleatórios em um rubi moderno é:

(0..50).to_a.shuffle.take(x)

Answer 3

Só para se ter uma idéia sobre a velocidade, eu corri quatro versões deste:

1. Usando conjuntos, como a sugestão de Ryan.
2. usando uma matriz ligeiramente maior do que o necessário, em seguida, fazendo uniq! no final.
3. Usar uma Hash, como Kyle sugeriu.
4. Como criar uma matriz do tamanho necessário, em seguida, classificando-o de forma aleatória, como a sugestão de Kent (mas sem o estranho "- 0.5", que não faz nada).

Eles são todos rápido em pequenas escalas, então eu tive-los cada criar uma lista de 1.000.000 números. Aqui estão os tempos, em segundos:

1. Conjuntos: 628
2. Matriz + uniq: 629
3. Hash: 645
4. array fixo + tipo: 8

E não, essa última não é um erro de digitação. Então, se você se preocupa com velocidade, e é OK para os números para ser inteiros de 0 a qualquer outra coisa, então o meu código exato foi:

a = (0...1000000).sort_by{rand}

Answer 4

rubi 1,9 ofertas o método amostra Array # que retorna um elemento ou elementos seleccionados aleatoriamente a partir de uma matriz. Os resultados do #sample não irá incluir o mesmo elemento de matriz duas vezes.

(1..999).to_a.sample 5 # => [389, 30, 326, 946, 746]

Quando comparado com a abordagem to_a.sort_by, o método sample parece ser significativamente mais rápido. Em um cenário simples eu comparei sort_by para sample, e obteve os seguintes resultados.

require 'benchmark'
range = 0...1000000
how_many = 5

Benchmark.realtime do
  range.to_a.sample(how_many)
end
=> 0.081083

Benchmark.realtime do
  (range).sort_by{rand}[0...how_many]
end
=> 2.907445

Answer 5

Sim, é possível fazer isso sem um loop e sem manter o controle de quais números foram escolhidos. É chamado de Linear de Feedback Shift Register: Criar Random Number Sequence com SEM repetições

Answer 6

Que tal um jogo sobre este assunto? números aleatórios exclusivos sem precisar usar Set ou hash.

x = 0
(1..100).map{|iter| x += rand(100)}.shuffle

Answer 7

Você pode usar um hash para rastrear os números aleatórios que você usou até agora:

seen = {}
max = 100
(1..10).map { |n|
  x = rand(max)
  while (seen[x]) 
    x = rand(max)
  end
  x
}

Answer 8

Em vez de adicionar os itens a uma lista / array, adicioná-los a uma Set.

Answer 9

Se você tem uma lista finita de possíveis números aleatórios (ou seja, 1 a 100), então a solução da Kent é bom.

Caso contrário, não há outra boa maneira de fazê-lo sem loop. O problema é que você deve fazer um loop se você receber um duplicado. Minha solução deve ser eficiente e o looping não deve ser muito muito mais do que o tamanho de sua matriz (ou seja, se você quiser 20 números aleatórios exclusivos, pode demorar 25 iterações, em média.) Embora o número de iterações piorar as mais números precisa eo máximo menor é. Aqui está o meu código acima modificado para mostrar quantas iterações são necessárias para a entrada de dados:

require 'set'

def rand_n(n, max)
    randoms = Set.new
    i = 0
    loop do
        randoms << rand(max)
        break if randoms.size > n
        i += 1
    end
    puts "Took #{i} iterations for #{n} random numbers to a max of #{max}"
    return randoms.to_a
end

Eu poderia escrever este código se parecer mais com Array.map se quiser:)

Answer 10

Com base na solução de Kent Fredric acima, isso é o que eu acabei usando:

def n_unique_rand(number_to_generate, rand_upper_limit)
  return (0..rand_upper_limit - 1).sort_by{rand}[0..number_to_generate - 1]
end

Graças Kent.

Answer 11

Sem laços com este método

Array.new(size) { rand(max) }

require 'benchmark'
max = 1000000
size = 5
Benchmark.realtime do
  Array.new(size) { rand(max) }
end

=> 1.9114e-05 

Answer 12

Aqui está uma solução:

Suponha que você queira esses números aleatórios para estar entre r_min e r_max. Para cada elemento na sua lista, gerar um r número aleatório, e fazer list[i]=list[i-1]+r. Isto lhe daria números aleatórios que são monótona crescente, garantindo exclusividade, desde que

• r+list[i-1] não sobre o fluxo
• r> 0

Para o primeiro elemento, você usaria r_min vez de list[i-1]. Assim que estiver pronto, você pode embaralhar a lista de modo que os elementos não são tão obviamente em ordem.

O único problema com este método é quando você passar por cima r_max e ainda ter mais elementos para gerar. Neste caso, você pode redefinir r_min e r_max a 2 elemento adjacente você já calculado, e basta repetir o processo. Isso efetivamente executa o mesmo algoritmo em um intervalo onde não existem números já utilizados. Você pode continuar fazendo isso até que você tenha a lista povoada.

Answer 13

Na medida em que é bom saber com antecedência o valor maxium, você pode fazer desta maneira:

class NoLoopRand
  def initialize(max)
    @deck = (0..max).to_a
  end

  def getrnd
    return @deck.delete_at(rand(@deck.length - 1))
  end
end

e você pode obter dados aleatórios da seguinte maneira:

aRndNum = NoLoopRand.new(10)
puts aRndNum.getrnd

você vai obter nil quando todos os valores serão exausted do baralho.

Answer 14

Método 1

Usando a abordagem de Kent, é possível gerar uma matriz de comprimento arbitrário manter todos os valores em uma gama limitada:

# Generates a random array of length n.
#
# @param n     length of the desired array
# @param lower minimum number in the array
# @param upper maximum number in the array
def ary_rand(n, lower, upper)
    values_set = (lower..upper).to_a
    repetition = n/(upper-lower+1) + 1
    (values_set*repetition).sample n
end

Método 2

Outro, possivelmente mais eficiente , o método modificado a partir do mesmo Kent outra resposta :

def ary_rand2(n, lower, upper)
    v = (lower..upper).to_a
    (0...n).map{ v[rand(v.length)] }
end

saída

puts (ary_rand 5, 0, 9).to_s # [0, 8, 2, 5, 6] expected
puts (ary_rand 5, 0, 9).to_s # [7, 8, 2, 4, 3] different result for same params
puts (ary_rand 5, 0, 1).to_s # [0, 0, 1, 0, 1] repeated values from limited range
puts (ary_rand 5, 9, 0).to_s # []              no such range :)