python - 制作反向五星级评级计算器的最佳方法

Question

在 5 星评级系统中，我有一个已知的评级数 N(投票数。)
我还有所有这些 N 个评级的最终(加权)平均值，假设它是 R( float 到小数点后两位)。
我想知道生成所有可能组合(加权平均值总计)并仅打印出导致 R 的组合的最佳方法(算法)。打印“所有”可能组合不是我想要的，因为对于大 N 和小 R，它将运行数百亿。我距离成为 Python 新手仅一步之遥，但它将是首选语言，而这个练习正是我对该语言的介绍。解决这个问题的最佳方法是什么？方法是我的问题，但非常感谢任何代码提示。

示例:

N= 20 位客户对产品进行了评分
R = 3.85 是平均评分

输出:[14, 0, 0, 1, 5]是 146 种可能的组合。“五星级14家，四星级0家，三星级0家，二星级1家，一星5家”

以及组合:[487, 0, 1, 0, 12]对于 N=500 和 R=4.90 等，是 1154 种可能的组合。

Answer 1

星星总数为 N*R(在您的示例中为 20 * 3.85 = 77)。现在你有类似于 the change making problem 的东西除了你的硬币总数是固定的。

一个有效的解决方案可能是从尽可能多的大硬币(5 星评级)开始，不会超过总数，然后逐渐减少，直到您的评级不会超过总数。您最终仍然会检查不起作用的解决方案，但这比检查所有解决方案要快得多，尤其是对于大型问题。

这是我的解决方案:(编辑:已调试解决方案。我不认为它是最佳解决方案，但它比蛮力更好。1931 年递归调用 N=20 R=3.85 的示例案例)

def distribution(total, maxRating, N, solution):
    if total == 0 and N == 0:
        return [solution + [0] * maxRating] #we found a solution

    if total == 0 or N == 0:
        return [] # no solution possible

    largestUpperLimit = min(total // maxRating, N) # an upper limit for the number of reviews with the largest rating
    largestLowerLimit = max((total - N * (maxRating -1)) // maxRating, 0) # a lower limit for the number of reviews with the largest rating

    if N < largestLowerLimit:
        return [] # there aren't enough ratings to make any solutions
    else:
        solutions = []
        for i in range(largestLowerLimit, largestUpperLimit + 1): # plus 1 to include the upper limit
            solutions.extend(distribution(total - i * maxRating, maxRating - 1, N - i, solution + [i]))
        return solutions


# Using the function example:
solutions = distribution(N * R, 5, N, [])