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

Question

Это то, что я имею до сих пор:

myArray.map!{ rand(max) }

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

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

Answer 1

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

(0..50).to_a можно заменить любым массивом. 0 - это «минимальное значение», 50 - «максимальное значение» х это "сколько значений я хочу"

конечно, невозможно, чтобы х было разрешено превышать 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)

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

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

Answer 2

Это использует 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 3

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

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

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

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

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

1. Наборы: 628
2. Array + uniq: 629
3. Хеш: 645
4. исправлено Array + sort: 8

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

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

Answer 5

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

Answer 6

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

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

Answer 7

Нет циклов с этим методом

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

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

=> 1.9114e-05 

Answer 8

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

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

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

Answer 10

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