arrays - 在 49 次抽奖中检查一组 6 个号码中的 3 的匹配情况

问题描述

我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

标签： arraysrubyoptimizationsetcombinations

假设所有的needle都是的成员all_numbers：

三个是正确的，这是 6 的 3 组合：

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

对于其余三个不正确的情况，这是其余 (49-6) 的 3 组合：

(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(with require 'set')，具体取决于您要生成的内容。

arrays - 在 49 次抽奖中检查一组 6 个号码中的 3 的匹配情况

问题描述

解决方案

推荐阅读