主页 / coding / 问题 / 78525363
Accepted
JustLearning
Asked: 2024-05-24 04:09:41 +0800 CST

复合分数算法

  • 772

我有一组 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
    }
}

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

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

python

1 个回答

  1. Best Answer

    这是一个递归解决方案。我注意到每种化合物的原始混合比加到 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

相关问题