复合分数算法

Question

我有一组 N 种化合物，分别为 1, 2,..., N。对于每种化合物，我都有其每种成分的分数，“A”，“B”等。化合物还可以包含其他化合物，在这种情况下给出相应的分数。例如，对于 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
    }
}

我目前的方法涉及递归，但我想知道是否有一个聪明的方法来做到这一点。也许使用树状数据结构可能会有所帮助？

编辑： 为简单起见，假设数据集中没有循环关系。

Answer 1

这是一个递归解决方案：

from collections import defaultdict
from pprint import pprint

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

# A dictionary of dictionaries with default 0.0 float values.
result = defaultdict(lambda: defaultdict(float))

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

for compound in mixes:
    for component, ratios in resolve(compound):
        result[compound][component] += ratios

pprint(result, width=20)

输出：

defaultdict(<function <lambda> at 0x000002632319B9C0>,
            {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})})