Алгоритм Deep Hash Invert (должен быть в ruby)
У меня есть хэш H (см. внизу) и необходимо выполнить операцию глубокого инвертирования, чтобы новый хеш H2 возвращается, где каждый ключ K значение внутри исходного хэша Ключи в H2 отобразить в массив массивов всех последовательностей ключей, которые при применении к исходному хешу H даст вам ключ K который является значением в оригинальном хеше.
Возможно, мне следует использовать другую структуру данных для вывода, например, хэш хэшей?
Я бы хотел, чтобы это работало с хэшами произвольных уровней вложенности.
Я не знаю, с чего начать разработку оптимального алгоритма
Оригинальный хэш
Как может выглядеть вход
{
u: {
u: { u: :phe, c: :phe, a: :leu, g: :leu },
c: { u: :ser, c: :ser, a: :ser, g: :ser },
a: { u: :tyr, c: :tyr, a: :STOP, g: :STOP },
g: { u: :cys, c: :cys, a: :STOP, g: :trp }
},
c: {
u: { u: :leu, c: :leu, a: :leu, g: :leu },
c: { u: :pro, c: :pro, a: :pro, g: :pro },
a: { u: :his, c: :his, a: :gln, g: :gln },
g: { u: :arg, c: :arg, a: :arg, g: :arg }
},
{...}
}
Упрощенный вывод
Какой вывод будет выглядеть
{
phe: [[:u,:u,:u],[:u,:u,:c]],
leu: [[:u,:u,:a],[:u,:u,:g]],
ser: [[:u,:c,:u],[:u,:c,:c],[:u,:u,:a],[:u,:u,:g]],
tyr: [[:u,:a,:u],[:u,:a,:c]],
"...": [[...]]
}
Зачем? Я пишу свою собственную библиотеку биоинформатики и хочу иметь возможность возвращать возможные нуклеотидные последовательности для данного белка, обозначенные тремя символами :symbols
1 ответ
Решение
Код
def recurse(h, arr=[])
h.each_with_object({}) { |(k,v),g| g.update((Hash===v) ?
recurse(v, arr + [k]) : { v=>[arr+[k]] }) { |_,o,n| o+n } }
end
В рекурсии используется форма Hash # update (aka merge!) который использует блок { |_,o,n| o+n } } определить значения ключей, которые присутствуют в обоих объединяемых хешах.
Пример 1
h =
{
u: {
u: { u: :phe, c: :phe, a: :leu, g: :leu },
c: { u: :ser, c: :ser, a: :ser, g: :ser },
a: { u: :tyr, c: :tyr, a: :STOP, g: :STOP },
g: { u: :cys, c: :cys, a: :STOP, g: :trp }
},
c: {
u: { u: :leu, c: :leu, a: :leu, g: :leu },
c: { u: :pro, c: :pro, a: :pro, g: :pro },
a: { u: :his, c: :his, a: :gln, g: :gln },
g: { u: :arg, c: :arg, a: :arg, g: :arg }
},
}
recurse h
#=> {:phe=>[[:u, :u, :u], [:u, :u, :c]],
# :leu=>[[:u, :u, :a], [:u, :u, :g], [:c, :u, :u],
# [:c, :u, :c], [:c, :u, :a], [:c, :u, :g]],
# :ser=>[[:u, :c, :u], [:u, :c, :c], [:u, :c, :a], [:u, :c, :g]],
# :tyr=>[[:u, :a, :u], [:u, :a, :c]],
# :STOP=>[[:u, :a, :a], [:u, :a, :g], [:u, :g, :a]],
# :cys=>[[:u, :g, :u], [:u, :g, :c]],
# :trp=>[[:u, :g, :g]],
# :pro=>[[:c, :c, :u], [:c, :c, :c], [:c, :c, :a], [:c, :c, :g]],
# :his=>[[:c, :a, :u], [:c, :a, :c]],
# :gln=>[[:c, :a, :a], [:c, :a, :g]],
# :arg=>[[:c, :g, :u], [:c, :g, :c], [:c, :g, :a], [:c, :g, :g]]}
Пример 2
h =
{
u: {
u: { u: :phe, a: :leu },
c: { u: :ser, c: :phe },
a: { u: :tyr, c: { a: { u: :leu, c: :ser }, u: :tyr } }
},
c: {
u: { u: :leu, c: :pro },
a: { u: :arg }
},
}
recurse(h)
#=> {:phe=>[[:u, :u, :u], [:u, :c, :c]],
# :leu=>[[:u, :u, :a], [:u, :a, :c, :a, :u], [:c, :u, :u]],
# :ser=>[[:u, :c, :u], [:u, :a, :c, :a, :c]],
# :tyr=>[[:u, :a, :u], [:u, :a, :c, :u]],
# :pro=>[[:c, :u, :c]], :arg=>[[:c, :a, :u]]}
объяснение
Вот код, измененный для отображения выполняемых вычислений:
def recurse(h, arr=[], level = 0)
indent = ' '*(2*level)
puts "#{indent}level = #{level}"
puts "#{indent}h= #{h}"
puts "#{indent}arr= #{arr}"
g = h.each_with_object({}) do |(k,v),g|
puts "#{indent} level = #{level}"
puts "#{indent} k=#{k}"
puts "#{indent} v=#{v}"
puts "#{indent} g=#{g}"
case v
when Hash
puts "#{indent} v is Hash"
g.update(recurse(v, arr + [k], level+1)) { |_,o,n| o+n }
else
puts "#{indent} v is not a Hash"
g.update({ v=>[arr+[k]] }) { |_,o,n| o+n }
end
end
puts "#{indent}return #{g}"
g
end
Выход для recurse h следует, для примера 2 (только для несгибаемых).
level = 0
h= {:u=>{:u=>{:u=>:phe, :a=>:leu}, :c=>{:u=>:ser, :c=>:phe}, :a=>{:u=>:tyr, :c=>{:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}}}, :c=>{:u=>{:u=>:leu, :c=>:pro}, :a=>{:u=>:arg}}}
arr= []
level = 0
k=u
v={:u=>{:u=>:phe, :a=>:leu}, :c=>{:u=>:ser, :c=>:phe},
:a=>{:u=>:tyr, :c=>{:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}}}
g={}
v is Hash
level = 1
h= {:u=>{:u=>:phe, :a=>:leu}, :c=>{:u=>:ser, :c=>:phe},
:a=>{:u=>:tyr, :c=>{:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}}}
arr= [:u]
level = 1
k=u
v={:u=>:phe, :a=>:leu}
g={}
v is Hash
level = 2
h= {:u=>:phe, :a=>:leu}
arr= [:u, :u]
level = 2
k=u
v=phe
g={}
v is not a Hash
level = 2
k=a
v=leu
g={:phe=>[[:u, :u, :u]]}
v is not a Hash
return {:phe=>[[:u, :u, :u]], :leu=>[[:u, :u, :a]]}
level = 1
k=c
v={:u=>:ser, :c=>:phe}
g={:phe=>[[:u, :u, :u]], :leu=>[[:u, :u, :a]]}
v is Hash
level = 2
h= {:u=>:ser, :c=>:phe}
arr= [:u, :c]
level = 2
k=u
v=ser
g={}
v is not a Hash
level = 2
k=c
v=phe
g={:ser=>[[:u, :c, :u]]}
v is not a Hash
return {:ser=>[[:u, :c, :u]], :phe=>[[:u, :c, :c]]}
level = 1
k=a
v={:u=>:tyr, :c=>{:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}}
g={:phe=>[[:u, :u, :u], [:u, :c, :c]], :leu=>[[:u, :u, :a]], :ser=>[[:u, :c, :u]]}
v is Hash
level = 2
h= {:u=>:tyr, :c=>{:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}}
arr= [:u, :a]
level = 2
k=u
v=tyr
g={}
v is not a Hash
level = 2
k=c
v={:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}
g={:tyr=>[[:u, :a, :u]]}
v is Hash
level = 3
h= {:a=>{:u=>:leu, :c=>:ser}, :u=>:tyr}
arr= [:u, :a, :c]
level = 3
k=a
v={:u=>:leu, :c=>:ser}
g={}
v is Hash
level = 4
h= {:u=>:leu, :c=>:ser}
arr= [:u, :a, :c, :a]
level = 4
k=u
v=leu
g={}
v is not a Hash
level = 4
k=c
v=ser
g={:leu=>[[:u, :a, :c, :a, :u]]}
v is not a Hash
return {:leu=>[[:u, :a, :c, :a, :u]], :ser=>[[:u, :a, :c, :a, :c]]}
level = 3
k=u
v=tyr
g={:leu=>[[:u, :a, :c, :a, :u]], :ser=>[[:u, :a, :c, :a, :c]]}
v is not a Hash
return {:leu=>[[:u, :a, :c, :a, :u]], :ser=>[[:u, :a, :c, :a, :c]],
:tyr=>[[:u, :a, :c, :u]]}
return {:tyr=>[[:u, :a, :u], [:u, :a, :c, :u]], :leu=>[[:u, :a, :c, :a, :u]],
:ser=>[[:u, :a, :c, :a, :c]]}
return {:phe=>[[:u, :u, :u], [:u, :c, :c]], :leu=>[[:u, :u, :a], [:u, :a, :c, :a, :u]],
:ser=>[[:u, :c, :u], [:u, :a, :c, :a, :c]], :tyr=>[[:u, :a, :u], [:u, :a, :c, :u]]}
level = 0
k=c
v={:u=>{:u=>:leu, :c=>:pro}, :a=>{:u=>:arg}}
g={:phe=>[[:u, :u, :u], [:u, :c, :c]], :leu=>[[:u, :u, :a], [:u, :a, :c, :a, :u]],
:ser=>[[:u, :c, :u], [:u, :a, :c, :a, :c]], :tyr=>[[:u, :a, :u], [:u, :a, :c, :u]]}
v is Hash
level = 1
h= {:u=>{:u=>:leu, :c=>:pro}, :a=>{:u=>:arg}}
arr= [:c]
level = 1
k=u
v={:u=>:leu, :c=>:pro}
g={}
v is Hash
level = 2
h= {:u=>:leu, :c=>:pro}
arr= [:c, :u]
level = 2
k=u
v=leu
g={}
v is not a Hash
level = 2
k=c
v=pro
g={:leu=>[[:c, :u, :u]]}
v is not a Hash
return {:leu=>[[:c, :u, :u]], :pro=>[[:c, :u, :c]]}
level = 1
k=a
v={:u=>:arg}
g={:leu=>[[:c, :u, :u]], :pro=>[[:c, :u, :c]]}
v is Hash
level = 2
h= {:u=>:arg}
arr= [:c, :a]
level = 2
k=u
v=arg
g={}
v is not a Hash
return {:arg=>[[:c, :a, :u]]}
return {:leu=>[[:c, :u, :u]], :pro=>[[:c, :u, :c]], :arg=>[[:c, :a, :u]]}
return {:phe=>[[:u, :u, :u], [:u, :c, :c]],
:leu=>[[:u, :u, :a], [:u, :a, :c, :a, :u], [:c, :u, :u]],
:ser=>[[:u, :c, :u], [:u, :a, :c, :a, :c]],
:tyr=>[[:u, :a, :u], [:u, :a, :c, :u]],
:pro=>[[:c, :u, :c]],
:arg=>[[:c, :a, :u]]}
#=> <the last value returned above>