2

给定一个模块数组，返回一个描述模块之间规范化（最小）排序关系的数组的最佳方法是什么？数组的每个元素都应该是具有父子关系的模块对数组。每对中的子父顺序很重要，但对之间的顺序无关紧要。归一化排序意味着任何可以从传递性派生的东西都应该从数组中排除。

例如，给定[Object, Comparable, Float, Fixnum, Integer]，答案将是：

[
  [Float, Object],
  [Float, Comparable],
  [Fixnum, Integer],
  [Integer, Object],
  [Integer, Comparable],
]

数组中的五对对应于该哈斯图中的五条边： 哈斯图

提示：如果存在顺序关系，则Module#<=>other返回-1, 0，如果不存在顺序关系。1nil

4

2 回答 2

3 
def ordering(mods)
  a = mods.permutation(2)
          .select { |m1,m2| (m1<=>m2) == -1 }
  a.reject { |m1,m2|
      mods.any? { |m| a.include?([m1,m]) && a.include?([m,m2]) } }
end

ordering([Object, Comparable, Float, Fixnum, Integer])
  #=> [[Float, Object],
  #    [Float, Comparable],
  #    [Fixnum, Integer],
  #    [Integer, Object],
  #    [Integer, Comparable]] 


mods = [Object, Comparable, Float, Fixnum, Integer, String, Array,
        Hash, Enumerable, Enumerator, Module, Method, IO, File]
ordering(mods)
  #=> [[Float, Object], [Float, Comparable],
  #    [Fixnum, Integer],
  #    [Integer, Object], [Integer, Comparable],
  #    [String, Object], [String, Comparable],
  #    [Array, Object], [Array, Enumerable],
  #    [Hash, Object], [Hash, Enumerable], [Hash, Object],
  #      [Hash, Enumerable],
  #    [Enumerator, Object], [Enumerator, Enumerable],
  #    [Module, Object],
  #    [Method, Object],
  #    [IO, Object], [IO, Enumerable],
  #    [File, IO]]
于 2015-02-10T09:14:57.787 回答
1

看来我可以介绍解决方案。它远非优雅，但您可能会发现此代码的某些部分可用作提示。

我不会使用模块比较。

input = [Object, Comparable, Float, Fixnum, Integer]

首先，让我们提供一个函数来构建一个完整的类/模块supers列表：

def grands klass
  klasses = klass.included_modules
  loop do
    break unless \
       klass.methods.include?(:superclass) && \
       (klass = klass.superclass)
    klasses << klass
  end 
  klasses
end

现在我们将收集所有向前和向后的后代：

result = input.reduce({:fwd => {}, :bwd => {}}) { |memo, klass|
  grands(klass).each { |c| 
    next unless input.include? c
    (memo[:fwd][klass] ||= []) << c 
    (memo[:bwd][c] ||= []) << klass
  }
  memo
}
p result

# NB Below is the output of input _including_ Numeric in demo purposes

# { :fwd => {
#     Float   => [Comparable, Numeric, Object],
#     Fixnum  => [Comparable, Integer, Numeric, Object],
#     Numeric => [Comparable, Object],
#     Integer => [Comparable, Numeric, Object]
#   },
#   :bwd => {
#     Comparable => [Float, Fixnum, Numeric, Integer],
#     Numeric    => [Float, Fixnum, Integer],
#     Object     => [Float, Fixnum, Numeric, Integer],
#     Integer    => [Fixnum]
#   }
# }

是时候构建标准化哈希了：

normalized = Hash[result[:fwd].map { |k, v|
  [k, v.select { |c|
    (result[:bwd][c] & v).empty?
  }]
}]

这给出了：

# {  
#    Float   => [Comparable, Object], 
#    Fixnum  => [Integer], 
#    Integer => [Comparable, Object]
# }

您请求了一个数组作为结果；转换非常简单，绝对超出了此任务的范围。

希望能帮助到你。

于 2015-02-10T08:37:27.173 回答