Как мне сгенерировать список из n уникальных случайных чисел в Ruby?

Question

Это то, что у меня есть на данный момент:

myArray.map!{ rand(max) }

Однако очевидно, что иногда номера в списке не уникальны.Как я могу убедиться, что мой список содержит только уникальные номера, без необходимости создавать больший список, из которого я затем просто выбираю n уникальных номеров?

Редактировать:
Мне бы очень хотелось, чтобы это было сделано без цикла - если это вообще возможно.

Answer 1

При этом используется 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 может быть заменен любым массивом.0 - "минимальное значение", 50 - "максимальное значение" x - "сколько значений я хочу вывести".

конечно, невозможно, чтобы значение x было больше max-min :)

В расширении того, как это работает

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

Примечания:

Стоит отметить, что в то время, когда на этот вопрос был дан первоначальный ответ, в сентябре 2008 года, было сказано, что Array#shuffle был либо недоступен, либо еще не известен мне, следовательно, приближение в Array#sort

И в результате появляется шквал предлагаемых правок по этому поводу.

Итак:

.sort{ rand() - 0.5 }

Может быть лучше и короче выражено в современных реализациях ruby с использованием

.shuffle

Дополнительно,

[0..x]

Может быть более очевидно написано с помощью Array#take как:

.take(x)

Таким образом, самый простой способ создать последовательность случайных чисел на современном ruby - это:

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

Answer 3

Просто чтобы дать вам представление о скорости, я запустил четыре версии этого:

1. Используя наборы, как предложил Райан.
2. Используя массив немного большего размера, чем необходимо, затем выполняя uniq!в конце концов.
3. Используя Хэш, как предложил Кайл.
4. Создаем массив требуемого размера, затем сортируем его случайным образом, как предложил Кент (но без постороннего "- 0.5", который ничего не делает).

Все они быстры в небольших масштабах, поэтому я попросил каждого из них создать список из 1 000 000 чисел.Вот время, выраженное в секундах:

1. Наборы:628
2. Массив + uniq:629
3. Хэш:645
4. фиксированный массив + сортировка:8

И нет, последнее - не опечатка.Так что, если вас волнует скорость, и это нормально, если числа должны быть целыми числами от 0 до чего угодно, то мой точный код был:

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

Answer 4

Ruby 1.9 предлагает метод Array#sample, который возвращает элемент или элементы, случайно выбранные из массива.Результаты #sample не будут включать один и тот же элемент массива дважды.

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

По сравнению с to_a.sort_by подход, основанный на sample метод, по-видимому, значительно быстрее.В простом сценарии я сравнил sort_by Для sample, и получил следующие результаты.

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

Да, это можно сделать без цикла и без отслеживания того, какие числа были выбраны.Это называется Регистром сдвига с линейной обратной связью: Создайте Последовательность случайных чисел без Повторов

Answer 6

Как насчет того, чтобы сыграть на этом?Уникальные случайные числа без необходимости использования Set или Hash.

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

Answer 7

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

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

Answer 8

Вместо того чтобы добавлять элементы в список / массив, добавьте их в набор.

Answer 9

Если у вас есть конечный список возможных случайных чисел (т. е.от 1 до 100), тогда решение Кента хорошее.

В противном случае нет другого хорошего способа сделать это без зацикливания.Проблема в том, что вы ДОЛЖНЫ выполнить цикл, если получите дубликат.Мое решение должно быть эффективным, и цикл не должен быть слишком большим, чем размер вашего массива (т. е.если вам нужно 20 уникальных случайных чисел, в среднем может потребоваться 25 итераций.) Хотя количество итераций увеличивается с увеличением количества чисел, которые вам нужны, и с уменьшением максимального значения.Вот мой приведенный выше код, измененный, чтобы показать, сколько итераций необходимо для данного ввода:

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

Я мог бы написать этот код, чтобы он больше походил на Array.map, если вы хотите :)

Answer 10

Основываясь на решении Кента Фредрика, приведенном выше, это то, что я в итоге использовал:

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

Спасибо, Кент.

Answer 11

В этом методе нет циклов

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

Вот одно из решений:

Предположим, вы хотите, чтобы эти случайные числа находились между r_min и r_max.Для каждого элемента в вашем списке сгенерируйте случайное число r, и сделать list[i]=list[i-1]+r.Это дало бы вам случайные числа, которые монотонно возрастают, гарантируя уникальность при условии, что

• r+list[i-1] не перетекает через край
• r > 0

Для первого элемента вы бы использовали r_min вместо того, чтобы list[i-1].Как только вы закончите, вы можете перетасовать список, чтобы элементы располагались не в таком очевидном порядке.

Единственная проблема с этим методом заключается в том, когда вы переходите r_max и еще нужно сгенерировать больше элементов.В этом случае вы можете выполнить сброс настроек r_min и r_max к 2 соседним элементам, которые вы уже вычислили, и просто повторите процесс.Это эффективно запускает тот же алгоритм на интервале, где еще нет используемых чисел.Вы можете продолжать делать это до тех пор, пока список не будет заполнен.

Answer 13

Поскольку приятно заранее знать максимальное значение, вы можете сделать это следующим образом:

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

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

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

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

вы получите nil когда все ценности будут извлечены из колоды.

Answer 14

Способ 1

Используя подход Кента, можно сгенерировать массив произвольной длины, сохраняя все значения в ограниченном диапазоне:

# 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

Способ 2

Другой, возможно более эффективный, метод, модифицированный по методу того же Кента другой ответ:

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

Выходной сигнал

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