2

モジュールの配列が与えられた場合、モジュール間の正規化された (最小限の) 順序関係を記述する配列を返す最良の方法は何ですか? 配列の各要素は、親子関係を持つモジュールのペアの配列でなければなりません。各ペア内の親子の順序は重要ですが、ペア間の順序は重要ではありません。正規化された順序付けとは、推移性から派生できるものはすべて配列から除外する必要があることを意味します。

たとえば、 が与えられた[Object, Comparable, Float, Fixnum, Integer]場合、答えは次のようになります。

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

配列内の 5 つのペアは、次のハッセ図の 5 つのエッジに対応します。 ハッセ線図

ヒント:順序関係がある場合は 、順序関係がない場合はをModule#<=>other返します。-101nil

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 に答える