ruby - Ruby 2.3.1 中 set 的除法函数

Question

以下内容来自 Ruby 2.3.1 文档，该文档根据应用于原始集合中每对元素的特定标准将集合划分为一组子集。基本上，如果集合中的两个数字彼此相差在 1 个单位以内，则它们属于原始集合的子集集合中的同一子集。

    require 'set'
numbers = Set[1, 3, 4, 6, 9, 10, 11]
set = numbers.divide { |i,j| (i - j).abs == 1 }
p set     # => #<Set: {#<Set: {1}>, 
          #            #<Set: {11, 9, 10}>,
          #            #<Set: {3, 4}>,

我认为我正在处理的问题可以使用此功能。这就是问题。有一个包含 n 个事物的集合 S 以及 S 中事物对的邻近函数，该集合中的某些事物对具有正值。对于未指定邻近函数值的对，可以假定这些值为 0。还有一个阈值参数。该程序的目标是在集合 S 上引入一个分区(一组成对不相交且相互穷举的集合子集)，使得如果两个事物的接近函数值超过阈值参数(相反不一定是真的)。​​

这个程序的输入是这样的形式

t<-阈值参数(大于0的 float )

n<- 后面的行数(整数)

Thing_i_1 Thing_j_1 proximity_ij_1(Thing_i_1 和 Thing_j_1 是整数，proximity_ij_1 是 float 且大于 0)

........Thing_i_n Thing_j_n proximity_ij_n

输出是前面提到的原始集合的成对不相交且相互穷举的子集集，使得接近函数值至少等于阈值参数的两个事物落入同一子集。

我编写了下面的程序来完成此操作，但它未能形成相关集合的子集。我的输入是这样的

0.2
3
1 2 0.3
3 4 0.1
2 5 0.25

输出应该是 {{1,2,5},{3},{4}} 因为 1,2 应该属于同一个子集，2,5 也应该属于同一个子集，因为每种情况下的邻近函数值都超过了阈值参数(所以 1 和 5 实际上属于同一个子集)，而 3 和 4 形成了它们自己的子集。

require 'set'
t=gets.chomp.to_f
n=gets.chomp.to_i
edge=Struct.new(:n1,:n2)
se=Array.new
af=Array.new
sv=Set.new

for i in (0..n-1)
    s=gets.chomp.split(" ")
    se.insert(-1,edge.new(s[0],s[1]))

        af.insert(-1,s[2].to_f)

    if (sv.member? s[0])==false 
        sv.add(s[0])
    end
    if (sv.member? s[1])==false 
        sv.add(s[1])
    end
end

    c=sv.divide { |i,j|  (k=se.index(edge.new(i,j)))!=nil  && af[k]>=t }
p c

输出:

#<Set: {#<Set: {"5"}>, #<Set: {"2"}>, #<Set: {"1"}>, #<Set: {"3"}>, #<Set: {"4"}
>}>

divide 函数似乎不起作用。我做错了什么吗？为什么我得到五个不相交的子集而不是预期的三个？我在除法 block 中打印出条件值，并准确地得到了 1,2 和 2,5，但 1、2 和 5 最终出现在不同的子集中。有人可以帮忙吗？谢谢。

Answer 1

divide只会划分block.call(a, b) && block.call(b, a) .让你的se自反(即也插入边 2-1、4-3 和 5-2)，它将起作用。或者，让你的 block 返回 true如果edge.new(i,j)或 edge.new(j, i)在se .还有一个关于类型的错误:您正在从字符串 ( edge.new(s[0],s[1]) ) 创建边缘，但是针对来自整数 ( edge.new(i,j) ) 的边缘进行测试，因此成员资格测试将失败。

也就是说，这是非常不符合 Rubyish 的代码。如果我要重写它，它会是这样的:

require 'set'

Edge = Struct.new(:v1, :v2, :p)
edges = {}
vertices = Set.new

t = gets.chomp.to_f
n = gets.chomp.to_i
n.times do
  v1, v2, p = *gets.chomp.split
  v1 = v1.to_i
  v2 = v2.to_i
  p = p.to_f
  edge = Edge.new(v1, v2, p)

  edges[[v1, v2]] = edge
  vertices << v1 << v2
end

c = vertices.divide { |v1, v2|
  (edge = edges[[v1, v2]] || edges[[v2, v1]]) && edge.p >= t
}

p c
# => #<Set: {#<Set: {1, 2, 5}>, #<Set: {3}>, #<Set: {4}>}>

基本上 - 使用散列以便您始终可以通过其索引快速找到边缘，使用 <<对于将事物放入其他事物，请记住集合的全部意义在于它不会两次插入相同的事物，对象是真实的，因此您不必显式测试 != nil , 从未使用过 for :)