2

以下内容来自 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<-threshold 参数（大于 0 的浮点数）

n<- 要遵循的行数（整数）

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

.... .... Thing_i_n Thing_j_nproximity_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"}
>}>

除法功能似乎不起作用。我做错什么了吗？为什么我得到五个不相交的子集而不是预期的三个？我在除法块中打印出条件的值，并且对于 1,2 和 2,5 完全正确，但 1、2 和 5 最终在不同的子集中。有人可以帮忙吗？谢谢你。

4

2 回答 2

1

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

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

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:)

于 2016-09-28T01:26:29.653 回答
0

编辑：我发现我回答了一个没有被问到的问题。我错误地认为，当[d,e]考虑接近度小于阈值时d，e如果存在来自d或e到达该集合的一个元素的“路径”，则将其添加到（部分构建的）集合之一。但是，我会留下我的答案，因为任何想要解决我已经解决的问题的人可能都会感兴趣。

这是另一种方式，它不使用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循环。我们现在构建一个s包含1和的连通集2。

(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}

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

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“连接”到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]

返回sets

sets
  #=> [#<Set: {1, 2, 5}>, #<Set: {6, 8, 10}>, #<Set: {3}>, #<Set: {4}>]
于 2016-09-28T17:49:32.467 回答