Проверьте совпадения с 3-мя в наборе из 6 чисел в 49 тиражах - PullRequest
Новая
       28

Проверьте совпадения с 3-мя в наборе из 6 чисел в 49 тиражах

0 голосов
/ 22 октября 2018

Я использую select в Sidekiq: 

require 'set'
require 'benchmark'

all_numbers = (1..49).to_a.combination(6)
needle = [1,2,3,4,5,6].to_set

Benchmark.bm do |x|
 x.report { all_numbers.select{|z| (needle & z).count == 3}  }
end

# user     system      total        real
# 74.200000   3.040000  77.240000 ( 78.901259)

Я хочу быстро проверить тысячи таких игл.Есть ли другой способ узнать эту информацию?Является ли преобразование в C одним из вариантов?

Примечание: all_numbers - это переменная, которая не изменяется и всегда является такой же, как указано выше.Цель состоит в том, чтобы отобразить все наборы, которые имеют 3 совпадения.Примеры игл можно получить из: 

(1..49).to_a.shuffle.first(6).sort

1 Ответ

0 голосов
/ 22 октября 2018

Предполагая, что все needle являются членами all_numbers:

Для правильных трех, это 3-комбинация из 6: 

(6*5*4) / (1*2*3) = 20

Для остальных трех добыть неправильным, это 3 комбинации из оставшихся (49-6): 

(43*42*41) / (1*2*3) = 12341

Таким образом, общее количество комбинаций равно 

12341 * 20 = 246820

В коде: 

require 'benchmark'

size_all = 49
size_needle = 6
required = 3

def binomial(n, k)
  ((n - k + 1)..n).inject(&:*) / (1..k).inject(&:*)
end

Benchmark.bm do |x|
  x.report {
    binomial(size_needle, required) * binomial(size_all - size_needle, required)
  }
end

#        user     system      total        real
#   0.000026   0.000006   0.000032 (  0.000030)

Немного быстрее.

РЕДАКТИРОВАТЬ: После изменения требований: 

class Array
  def semimatching_combination(needle, num_total, num_needle)
    unless block_given?
      return to_enum(__method__, needle, num_total, num_needle) do
        binomial(needle.size, num_needle) *
          binomial(self.size - needle.size, num_total - num_needle)
      end
    end

    needle.combination(num_needle) do |needle_comb|
      (self - needle).combination(num_total - num_needle) do |other_comb|
        yield (needle_comb + other_comb).sort
      end
    end
  end
end

(1..49).to_a.semimatching_combination((1..6).to_a, 6, 3).size
# => 246820
(1..49).to_a.semimatching_combination((1..6).to_a, 6, 3).to_a
# => [[1, 2, 3, 7, 8, 9], ...]

Вы можете заменить sort на to_set (с require 'set'), если хотите, в зависимости от того, что вы хотите сгенерировать.

...