创建 Class 关系

Question

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

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

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

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

提示: Module#<=>other returns -1, 0, 1 如果有订单关系，如果没有顺序关系，则 nil。

Answer 1

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

我不会使用模块比较。

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

首先，让我们提供一个函数来构建 class/module 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]
# }

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

希望对您有所帮助。

Answer 2

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]]

创建 Class 关系

Creating Class relation

ruby

class

module

subclass

poset