Ruby 2.3.1 中设置的除法函数

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。还有一个阈值参数。该程序的 objective 是在集合 S 上引入一个分区（一组成对不相交且相互穷举的集合子集），使得如果两个事物的邻近函数值超过阈值参数（反之不必为真）。

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

t<-阈值参数（大于0的浮点数）

n<- 后面的行数（整数）

Thing_i_1 Thing_j_1 proximity_ij_1（Thing_i_1 和 Thing_j_1 是整数，proximity_ij_1 是浮点数且大于 0）

..... .... Thing_i_n Thing_j_n proximity_ij_n

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

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

输出应该是 {{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"}
>}>

除法函数似乎不起作用。我做错了什么吗？为什么我得到五个不相交的子集而不是预期的三个？我在除法块中打印出条件值，并准确地得到了 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），它将起作用。或者，如果 edge.new(i,j) 或 edge.new(j, i) 在 se 中，则将您的区块设为 return true。还有一个关于类型的错误：你正在从字符串创建边（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 :)

Answer 2

编辑： 我发现我回答了一个没有被问到的问题。我错误地认为当 [d,e] 接近小于时考虑到 d 和 e 是要添加到其中一个（部分-built) 设置是否有来自 d 或 e 的 "path" 到该集合的一个元素。但是，我会留下我的答案，因为任何想要解决我所解决的问题的人可能会对它感兴趣。

这是另一种方式，它不使用 Set#divide。

代码

require 'set'

def setify(distances, threshold)
  sets = []
  g = distances.dup
  while (ret = g.find { |_,prox| prox >= threshold })
    (n1,n2),_ = ret
    s = [n1,n2].to_set
    g.delete [n1,n2]
    while (ret = g.find { |(n1,n2),_| s.include?(n1) || s.include?(n2) })
      pair,_ = ret
      s.merge pair   
      g.delete pair
    end
    sets << s
  end
  g.keys.flatten.each { |k| sets << [k].to_set }
  sets
end

例子

threshold = 0.2

distances = { [1,2]=>0.3, [3,4]=>0.1, [2,5]=>0.25 }
setify(distances, threshold)
  #=> [#<Set: {1, 2, 5}>, #<Set: {3}>, #<Set: {4}>] 

distances = { [1,2]=>0.3, [3,4]=>0.1, [6,8]=>0.2, [2,5]=>0.25, [8,10]=>0 }
setify(distances, threshold)
  #=> [#<Set: {1, 2, 5}>, #<Set: {6, 8, 10}>, #<Set: {3}>, #<Set: {4}>]

说明

假设

threshold = 0.2
distances = { [1,2]=>0.3, [3,4]=>0.1, [6,8]=>0.2, [2,5]=>0.25, [8,10]=>0 }

然后

sets = []
g = distances.dup
  #=> {[1, 2]=>0.3, [3, 4]=>0.1, [6, 8]=>0.2, [2, 5]=>0.25, [8, 10]=>0}

作为

ret = g.find { |_,prox| prox >= threshold }
  #=> [[1, 2], 0.3]

是真实的，我们进入（外部）while 循环。我们现在要构建一个包含 1 和 2.

的连通集 s

(n1,n2),_ = ret
  #=> [[1, 2], 0.3] 
s = [n1,n2].to_set
  #=> #<Set: {1, 2}>

由于 [n1,n2] 已被处理，我们必须从 g 中删除该键（因此，需要 g = distances.dup，以避免变异 distances）。

g.delete [n1,n2]
  #=> 0.3

让我们现在g看看。

g #=> {[3, 4]=>0.1, [6, 8]=>0.2, [2, 5]=>0.25, [8, 10]=>0}

现在在 g 中寻找另一个键 [a,b]（不是 'g' 的音乐键），这样 a 或 b (或两者）都在集合 s 中。如果找到这样的密钥，请尝试将 a 和 b 添加到 s 并从 g 中删除密钥 [a,b]。（至多该键的两个元素之一将被添加到集合中）。

ret = g.find { |(n1,n2),_| s.include?(n1) || s.include?(n2) }
  #=> [[2, 5], 0.25]

找到一个键值对，进入循环

pair,_ = ret
  #=> [[2, 5], 0.25]
pair
  #=> [2, 5] 
s.merge pair   
  #=> #<Set: {1, 2, 5}> 
g.delete pair
  #=> 0.25 
g
  #=> {[3, 4]=>0.1, [6, 8]=>0.2, [8, 10]=>0}

现在再次执行 while 表达式。

ret = g.find { |(n1,n2),_| s.include?(n1) || s.include?(n2) }
  #=> nil

因为 g 的键不再是 "connected" 到 s 的元素，我们将 s 添加到 sets，

sets << s
  #=> [#<Set: {1, 2, 5}>]

并期待在外循环中继续。

ret = g.find { |_,prox| prox >= threshold }
  #=> [[6, 8], 0.2]

我们找到了另一个集合的开始，其中至少有一对满足阈值，我们创建一个新集合并删除 g、

的关联键

(n1,n2),_ = ret
  #=> [[6, 8], 0.2]
n1 #=> 6
n2 #=> 8

s = [n1,n2].to_set
  #=> #<Set: {6, 8}> 
g.delete [n1,n2]
  #=> 0.2 
g #=> {[3, 4]=>0.1, [8, 10]=>0}

并着手构建那个集合。

ret = g.find { |(n1,n2),_| s.include?(n1) || s.include?(n2) }
  #=> [[8, 10], 0] 
pair,_ = ret
  #=> [[8, 10], 0] 
s.merge pair   
  #=> #<Set: {6, 8, 10}> 
g.delete pair
  #=> 0 
g #=> {[3, 4]=>0.1} 

ret = g.find { |(n1,n2),_| s.include?(n1) || s.include?(n2) }
  #=> nil

所以我们完成了集的构建 s。

sets << s
  #=> [#<Set: {1, 2, 5}>, #<Set: {6, 8, 10}>]

再次尝试进入外层循环（即看是否有另一组包含一对接近度满足阈值的元素）

ret = g.find { |_,prox| prox >= threshold }
  #=> nil

因此，g 中键的每个元素都必须包含它自己的集合。

b = g.keys
  #=> [[3, 4]] 
c = b.flatten
  #=> [3, 4] 
c.each { |k| sets << [k].to_set }
  #=> [3, 4]

Return sets

sets
  #=> [#<Set: {1, 2, 5}>, #<Set: {6, 8, 10}>, #<Set: {3}>, #<Set: {4}>]

Ruby 2.3.1 中设置的除法函数

divide function for set in Ruby 2.3.1

ruby

set

divide

ruby-2.3