Генерация случайных чисел пар чисел в диапазоне

Question

У меня неотрицательное целое число articles.length.Мне нужно создать список из n номеров неповторяющихся пар чисел в диапазоне 0...articles.length, т. Е. (Для articles.length == 10 и n == 5),

[[1, 3], [2, 6], [1, 6], [8, 1], [10, 3]]

Как мне это сделать?это?

Answer 1

Этого может быть достаточно, чтобы ответить на OP:

articles = ["apples","pencils","chairs","pencils","guitars","parsley", "ink","stuff" ]
n = 5
p random_pairs = Array.new(n){articles.sample(2) }

# => [["parsley", "apples"], ["pencils", "chairs"], ["pencils", "apples"], ["stuff", "apples"], ["stuff", "guitars"]]

Answer 2

Если вам нужно делать это регулярно, мы можем создать перечислитель, который сделает это за нас: (Спасибо @ CarySwoveland за концептуальную математику и использование Set)

require 'set'
def generator(limit,size=2) 
  enum_size = (limit.is_a?(Range) ? limit.size : limit += 1) ** size 
  if enum_size.infinite?
    limit = limit.is_a?(Range) ? (limit.first..Float::MAX.to_i) : Float::MAX.to_i
  end       
  Enumerator.new(enum_size) do |y| 
    s = Set.new
    loop do 
      new_rand = Array.new(size) { rand(limit) }
      y << new_rand if s.add?(new_rand)
      raise StopIteration if s.size == enum_size
    end
  end
end

Теперь получение n пар не требует от нас генерации всех возможных перестановок перед выборкой.Вместо этого мы генерируем n случайных пар по запросу.(не превышать максимально возможное количество перестановок).

Использование:

g = combination_generator(10)
g.take(5)
#=> [[10, 4], [9, 6], [9, 9], [2, 6], [4, 6]]
g.take(5)
#=> [[9, 7], [2, 8], [2, 2], [8, 8], [7, 3]]
g.to_a.sort
#=> [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [0, 9], [0, 10], 
#    [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10], 
# ..., [10,10]]

Работает с диапазонами, например generator((2..7)), будет генерировать комбинации только от [2,2] до [7,7].

Кроме того, я добавил возможность учесть любое количество элементов подмножества, не жертвуя скоростью генерации, например

g = generator((0..Float::INFINITY),20)
g.size 
#=>  Infinity 
g.first
#=> [20 extremely large numbers]
require 'benchmark'
Benchmark.bmbm do |x| 
  x.report(:fast) { g.first(10) } 
  x.report(:large_fast) { g.first(10_000) } 
end

# Rehearsal ----------------------------------------------
# fast         0.000552   0.000076   0.000628 (  0.000623)
# large_fast   0.612065   0.035515   0.647580 (  0.672739)
# ------------------------------------- total: 0.648208sec
#                  user     system      total        real
# fast         0.000728   0.000000   0.000728 (  0.000744)
# large_fast   0.598493   0.000000   0.598493 (  0.607784)

Answer 3

Расчет

mx = 10
n = 20
(0..(mx+1)**2-1).to_a.sample(n).map { |n| n.divmod(mx+1) }
  #=> [[6, 9], [3, 8], [7, 10], [3, 3], [2, 0], [8, 9], [4, 1], [9, 4], 
  #    [1, 0], [1, 8], [9, 6], [0, 10], [9, 0], [6, 8], [4, 9], [2, 10],
  #    [10, 0], [10, 5], [6, 10], [2, 9]]

Пояснение

Выборка пар чисел без замены аналогична выборке отдельных чисел без замены, когда между двумя есть карта 1-1.Думайте об одиночных числах как о двухзначных числах в базе mx+1, поэтому каждая цифра может находиться в диапазоне от 0 до mx, то есть соответствует одному элементу пары чисел, которые выбираются.Существуют (mx+1)**2 двузначные базовые mx+1 числа, которые в базе 10 варьируются от 0 до (mx+1)**2-1.Поэтому нам нужно всего лишь n раз от (0..(mx+1)**2-1).to_a, а затем использовать Integer # divmod , чтобы преобразовать каждое выбранное десятичное число обратно в две цифры из основного mx+1 числа (в базе 10).

Процедура явно объективна.

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

Если (mx+1)**2-1) достаточно велико по отношению к n, самый быстрый способ вполне может быть следующим (который также производит несмещенные сэмплы):

require 'set'

samp = Set.new
limit = mx+1
while samp.size < n
  samp << [rand(limit), rand(limit)]
end
samp.to_a
  #=> [[3, 6], [6, 2], [0, 3], [10, 0], [1, 8], [3, 4], [10, 3], [0, 4],
  #    [6, 7], [10, 7], [9, 1], [10, 5], [2, 7], [4, 8], [8, 4], [7, 3],
  #    [2, 4], [7, 10], [5, 3], [6, 3]]

Я обнаружил, что при рисовании случайных сэмплов 20 пар 100 раз (все для mx = 10), в среднем было сформировано 21.86 пар, чтобы после удаления дубликатов было оставлено 20 уникальных пар.

Тесты

Я думал, что это может бытьИнтересно сравнить несколько предложенных методов.

require 'benchmark'
require 'set'

Удобно поместить тестируемые методы в модуль ¹ .

module Candidates 
  def samp_with_difmod(mx, n)
    (0..(mx+1)**2-1).to_a.sample(n).map { |n| n.divmod(mx+1) }
  end

  def discard_dups(mx, n)
    samp = Set.new
    limit = mx+1
    while samp.size < n
      samp << [rand(limit), rand(limit)]
    end
    samp.to_a
  end

  def sawa_repeated_perm(mx, n)
    (0..mx).to_a.repeated_permutation(2).to_a.sample(n)
  end

  def sawa_product(mx, n)
    (0..mx).to_a.product((0..mx).to_a).sample(n)
  end
end

include Candidates
@candidates = Candidates.public_instance_methods(false)
  #=> [:samp_with_difmod, :discard_dups, :sawa_repeated_perm, :sawa_product]
@indent = candidates.map { |m| m.to_s.size }.max
  #=> 18

def bench(mx, n, reps)
  puts "\n0-#{mx}, sample size = #{n}, #{reps} reps"
  Benchmark.bm(@indent) do |bm|
    @candidates.each do |m|
      bm.report m.to_s do
        reps.times { send(m, mx, n) }
     end
    end
  end
end

bench(10, 20, 100)
0-10, sample size = 20, 100 reps
                         user     system      total        real
samp_with_difmod     0.000000   0.000000   0.000000 (  0.002536)
discard_dups         0.000000   0.000000   0.000000 (  0.005312)
sawa_repeated_perm   0.000000   0.000000   0.000000 (  0.004901)
sawa_product         0.000000   0.000000   0.000000 (  0.004742)

bench(100, 20, 100)
0-100, sample size = 20, 100 reps
                         user     system      total        real
samp_with_difmod     0.031250   0.015625   0.046875 (  0.088003)
discard_dups         0.000000   0.000000   0.000000 (  0.005618)
sawa_repeated_perm   0.093750   0.000000   0.093750 (  0.136010)
sawa_product         0.125000   0.000000   0.125000 (  0.138848)

bench(10, 121, 100)
0-10, sample size = 121, 100 reps
                         user     system      total        real
samp_with_difmod     0.000000   0.000000   0.000000 (  0.003283)
discard_dups         0.171875   0.015625   0.187500 (  0.208459)
sawa_repeated_perm   0.000000   0.000000   0.000000 (  0.004253)
sawa_product         0.000000   0.000000   0.000000 (  0.002947)

В приведенном выше примере выборка производится из населения 11**2 #=> 121.Получение выборки 121 без замены из совокупности 121 означает, что выборка состоит из всех пар в совокупности.Поэтому неудивительно, что discard_dups работает относительно плохо.Например, набрав 120 уникальных пар, он будет непрерывно отклонять дубликаты, пока не наткнется на оставшуюся пару, не попавшую в образец.

bench(100, 100, 100)
0-100, sample size = 100, 100 reps
                         user     system      total        real
samp_with_difmod     0.046875   0.000000   0.046875 (  0.042177)
discard_dups         0.031250   0.000000   0.031250 (  0.029467)
sawa_repeated_perm   0.109375   0.000000   0.109375 (  0.132429)
sawa_product         0.125000   0.000000   0.125000 (  0.140451)

bench(1000, 500, 10)
0-1000, sample size = 500, 10 reps
                         user     system      total        real
samp_with_difmod     0.437500   0.140625   0.578125 (  0.632434)
discard_dups         0.015625   0.000000   0.015625 (  0.013634)
sawa_repeated_perm   1.718750   0.359375   2.078125 (  2.166724)
sawa_product         1.734375   0.062500   1.796875 (  1.853555)

В этом последнем тесте, где максимальное значение (1000) является большим и большим по отношению к размеру выборки (500), discard_dups является явным победителем.Здесь размер выборочного пространства равен 1001**2 #=> 1_002_001, поэтому discard_dups может столкнуться с относительно небольшим количеством дубликатов при рисовании выборки размером 500.

sawa_product работает немного лучше, чем sawa_repeated_perm, нов других тестах производительность обоих методов одинакова.

^{1 Включение модуля, содержащего тестируемые методы, упрощает код и упрощает добавление, удаление и переименование тестируемых методов.}

Answer 4

Только если n <= s и если допустима пара, содержащая элементы равенства:

def random_pairs n, s
  res = []
  (1..n).to_a.tap { |a| res = a.sample(s).zip(a.sample(s)) }
  res
end

random_pairs 10, 5
#=> [[6, 5], [1, 1], [9, 6], [8, 4], [4, 7]]

Пары не повторяются, но может существовать пара, содержащая элементы равенства: [1,1]

---

Следоватькомментарии, но гораздо медленнее:

def random_pairs_bis n, s
  res = []
  s.times {(1..n).to_a.tap { |a| res << a.shuffle.zip(a.shuffle) }}
  res.flatten(1).uniq.sample(s)
end

Answer 5

Не самый эффективный, но работает следующее.

(0...10).to_a.repeated_permutation(2).to_a.sample(5)
#=> [[8, 4], [2, 9], [5, 0], [5, 4], [4, 3]]