Come faccio a generare un elenco di n numeri casuali univoci in Ruby?

Question

Questo è quello che ho finora:

myArray.map!{ rand(max) }

Ovviamente, tuttavia, a volte i numeri nell'elenco non sono univoci. Come posso assicurarmi che il mio elenco contenga solo numeri univoci senza dover creare un elenco più grande da cui scegliere solo i n numeri univoci?

Modifica
Mi piacerebbe davvero vederlo fatto senza loop, se possibile.

Answer 1

Questo utilizza 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 può essere sostituito con qualsiasi array. 0 è "valore minimo", 50 è "valore massimo" x è " quanti valori voglio "

ovviamente, è impossibile per x essere maggiore di max-min :)

In espansione di come funziona

(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 ]

Note:

Vale la pena ricordare che al momento della risposta a questa domanda, nel settembre 2008, Array # shuffle non era disponibile o non mi era già noto, quindi l'approssimazione in Array # sort

E di conseguenza c'è una raffica di modifiche suggerite a questo.

.sort{ rand() - 0.5 }

Può essere migliore e più breve espresso sulle implementazioni di rubini moderne usando

.shuffle

Inoltre,

[0..x]

Può essere più ovviamente scritto con Array # take come:

.take(x)

Quindi, il modo più semplice per produrre una sequenza di numeri casuali su un rubino moderno è:

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

Answer 3

Solo per darti un'idea della velocità, ho eseguito quattro versioni di questo:

1. Uso dei set, come il suggerimento di Ryan.
2. Usare un array leggermente più grande del necessario, quindi fare uniq! alla fine.
3. Usando un hash, come suggerito da Kyle.
4. Creazione di un array della dimensione richiesta, quindi ordinamento casuale, come il suggerimento di Kent (ma senza l'estraneo "0,5", che non fa nulla).

Sono tutti veloci su scala ridotta, quindi li ho fatti creare ciascuno un elenco di 1.000.000 di numeri. Ecco i tempi, in secondi:

1. Set: 628
2. Array + uniq: 629
3. Hash: 645
4. array fisso + ordinamento: 8

E no, l'ultimo non è un refuso. Quindi, se ti interessa la velocità, ed è OK che i numeri siano numeri interi da 0 a qualunque cosa, allora il mio codice esatto era:

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

Answer 4

Ruby 1.9 offre il metodo di esempio Array # che restituisce un elemento o elementi selezionati casualmente da un array. I risultati di #sample non includeranno due volte lo stesso elemento Array.

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

Rispetto all'approccio to_a.sort_by , il metodo sample sembra essere molto più veloce. In un semplice scenario ho confrontato sort_by con sample e ho ottenuto i seguenti risultati.

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

Sì, è possibile farlo senza un ciclo e senza tenere traccia di quali numeri sono stati scelti. Si chiama registro a scorrimento a feedback lineare: Crea sequenza di numeri casuali senza ripetizioni

Answer 6

Che ne dici di un gioco su questo? Numeri casuali univoci senza la necessità di utilizzare Set o Hash.

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

Answer 7

Puoi usare un hash per tenere traccia dei numeri casuali che hai usato finora:

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

Answer 8

Anziché aggiungere gli elementi a un elenco / array, aggiungerli a un set.

Answer 9

Se hai un elenco finito di possibili numeri casuali (cioè da 1 a 100), allora la soluzione di Kent è buona.

Altrimenti non c'è altro buon modo per farlo senza loop. Il problema è che DEVI fare un ciclo se ottieni un duplicato. La mia soluzione dovrebbe essere efficiente e il looping non dovrebbe essere molto più grande della dimensione del tuo array (cioè se vuoi 20 numeri casuali univoci, in media potrebbero essere necessarie 25 iterazioni). Sebbene il numero di iterazioni peggiori tanto più numeri bisogno e il più piccolo è. Ecco il mio codice sopra modificato per mostrare quante iterazioni sono necessarie per l'input dato:

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

Potrei scrivere questo codice per GUARDARE più come Array.map se vuoi :)

Answer 10

Basato sulla soluzione di Kent Fredric sopra, questo è quello che ho finito per usare:

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

Grazie Kent.

Answer 11

Nessun loop con questo metodo

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

Ecco una soluzione:

Supponi di voler inserire questi numeri casuali tra r_min e r_max . Per ogni elemento del tuo elenco, genera un numero casuale r e crea list [i] = list [i-1] + r . Questo ti darebbe numeri casuali che stanno aumentando monotonicamente, garantendo l'unicità a condizione che

• r + list [i-1] non trabocca
• r > 0

Per il primo elemento, dovresti usare r_min invece di list [i-1] . Una volta terminato, puoi mescolare l'elenco in modo che gli elementi non siano così ovviamente in ordine.

L'unico problema con questo metodo è quando vai su r_max e hai ancora più elementi da generare. In questo caso, puoi ripristinare r_min e r_max su 2 elementi adiacenti che hai già calcolato, e semplicemente ripetere il processo. Ciò esegue effettivamente lo stesso algoritmo su un intervallo in cui non ci sono numeri già utilizzati. Puoi continuare fino a quando l'elenco non viene popolato.

Answer 13

Per quanto è bello sapere in anticipo il valore massimo, puoi farlo in questo modo:

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

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

e puoi ottenere dati casuali in questo modo:

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

otterrai zero quando tutti i valori saranno esauriti dal mazzo.

Answer 14

Metodo 1

Utilizzando l'approccio di Kent, è possibile generare una matrice di lunghezza arbitraria mantenendo tutti i valori in un intervallo limitato:

# 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

Metodo 2

Un altro metodo, possibilmente più efficiente , modificato dallo stesso un'altra risposta :

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

uscita

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 :)