Алгоритм для сложных дробей
У меня есть набор из N химических соединений, пронумерованных 1, 2,..., N. Для каждого соединения у меня есть доля каждого из его компонентов: «А», «В» и так далее. Соединения могут также содержать другие соединения, в этом случае указывается соответствующая фракция. Например, для N = 5 набор выборок
mixes = {
1: {
"A": 0.32,
"B": 0.12,
"C": 0.15,
2: 0.41
},
2: {
"C": 0.23,
"D": 0.12,
"E": 0.51,
4: 0.14
},
3: {
"A": 0.24,
"E": 0.76
},
4: {
"B": 0.13,
"F": 0.01,
"H": 0.86
},
5: {
"G": 0.1,
2: 0.4,
3: 0.5
}
}
Мне нужен алгоритм, который дает чистую долю каждого компонента в каждом соединении, т.е.
mixes = {
1: {
"A": 0.32,
"B": 0.12 + 0.41 * 0.14 * 0.13,
"C": 0.15 + 0.41 * 0.23,
"D": 0.41 * 0.12,
"E": 0.41 * 0.51,
"F": 0.41 * 0.14 * 0.01,
"H": 0.41 * 0.14 * 0.86
},
2: {
"B": 0.14 * 0.13,
"C": 0.23,
"D": 0.12,
"E": 0.51,
"F": 0.14 * 0.01,
"H": 0.14 * 0.86
},
3: {
"A": 0.24,
"E": 0.76
},
4: {
"B": 0.13,
"F": 0.01,
"H": 0.86
},
5: {
"A": 0.5 * 0.24,
"G": 0.1,
"B": 0.4 * 0.14 * 0.13,
"C": 0.4 * 0.23,
"D": 0.4 * 0.12,
"E": 0.4 * 0.51 + 0.5 * 0.76,
"F": 0.4 * 0.14 * 0.01,
"H": 0.4 * 0.14 * 0.86
}
}
Мой нынешний подход предполагает рекурсию, но мне хотелось бы знать, есть ли умный способ сделать это. Возможно, поможет использование древовидной структуры данных?
Обновлено: для простоты предположим, что в наборе данных нет циклических связей.
Рекурсия - это путь. Но вы, конечно, все еще можете сделать это неэффективным способом...
Какие шаги вы предпринимаете, используя входные данные, чтобы рассчитать результаты вручную? Начните с четкого описания этих шагов словами, используя тот человеческий язык, который вам наиболее знаком.
Случай, когда вам не нужна (наивная) рекурсия, — это когда существуют циклические отношения.
Ответы 1
Вот рекурсивное решение. Я отметил, что исходные пропорции смеси для каждого соединения прибавляются к 1, поэтому есть также проверка того, что результирующие соединения также добавляются к 1:
from pprint import pprint
from collections import defaultdict
mixes = {
1: {
'A': 0.32,
'B': 0.12,
'C': 0.15,
2: 0.41
},
2: {
'C': 0.23,
'D': 0.12,
'E': 0.51,
4: 0.14
},
3: {
'A': 0.24,
'E': 0.76
},
4: {
'B': 0.13,
'F': 0.01,
'H': 0.86
},
5: {
'G': 0.1,
2: 0.4,
3: 0.5
}
}
def resolve(compound):
'''Return the components of a compound, recursively adjusted for ratios.
'''
for component, ratio in mixes[compound].items():
# If the component is another compound, recursively report its ratios.
if isinstance(component, int):
for subcomponent, subratio in resolve(component):
yield subcomponent, subratio * ratio
else:
yield component, ratio
# A dictionary of dictionaries with default 0.0 float values.
result = defaultdict(lambda: defaultdict(float))
# Resolve each compound and add up component ratios
for compound in mixes:
for component, ratio in resolve(compound):
result[compound][component] += ratio
pprint(result, width=1)
# Checking ratios of result compounds add up to 1
for compound, components in result.items():
print(compound, sum(component for component in components.values()))
Выход:
defaultdict(<function <lambda> at 0x00000214CD56FB00>,
{1: defaultdict(<class 'float'>,
{'A': 0.32,
'B': 0.127462,
'C': 0.2443,
'D': 0.049199999999999994,
'E': 0.20909999999999998,
'F': 0.0005740000000000001,
'H': 0.049364}),
2: defaultdict(<class 'float'>,
{'B': 0.0182,
'C': 0.23,
'D': 0.12,
'E': 0.51,
'F': 0.0014000000000000002,
'H': 0.12040000000000001}),
3: defaultdict(<class 'float'>,
{'A': 0.24,
'E': 0.76}),
4: defaultdict(<class 'float'>,
{'B': 0.13,
'F': 0.01,
'H': 0.86}),
5: defaultdict(<class 'float'>,
{'A': 0.12,
'B': 0.007280000000000001,
'C': 0.09200000000000001,
'D': 0.048,
'E': 0.5840000000000001,
'F': 0.0005600000000000001,
'G': 0.1,
'H': 0.04816000000000001})})
1 1.0
2 1.0
3 1.0
4 1.0
5 1.0
Спасибо за ваш ответ. Мой подход был очень похож, хотя рекурсивная функция не была генератором. Очень признателен!
Правило №1 программирования: не умничайте. У вас уже есть древовидная структура данных (на самом деле это DAG, но для целей этой задачи она работает так же, как дерево), и рекурсия — это способ справиться с ней.