Создание отношения класса

Question

Учитывая массив модулей, каков наилучший способ возврата массива, который описывает нормализованные (минимальные) отношения порядка между модулями? Каждый элемент массива должен быть массивом пар модулей, имеющих отношение родительский-родительский. Ребенок-родительский порядок в каждой паре имеет значение, но порядок между парами не имеет значения. Нормализованное упорядочение означает, что все, что может быть получено из транзитивности, должно быть исключено из массива.

Например, если [Object, Comparable, Float, Fixnum, Integer], ответ был бы:

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

пять пар в массиве соответствует пяти ребер в этой диаграммы Хассе:

Подсказка: Module#<=>other возвращается -1, 0, 1 если есть отношение к заказу, и nil если нет отношение к заказу.

Answer 1

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

Answer 2

Похоже, я мог бы представить решение. Это далеко не изящно, но вы можете найти некоторые части этого кода полезными в качестве подсказок.

Я не буду использовать сравнение модулей.

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

Прежде всего, давайте обеспечить функцию, чтобы построить целый список класса/модуля надставок:

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

Вы запросили массив в качестве результата; конверсия довольно проста и определенно выходит за рамки этой задачи.

Надеюсь, это поможет.