Best approach to make a reverse five-star calculator
<p>In the 5-star rating system, I have a known number of ratings.<br>
I have the final (weighted) average of all those N ratings, let's say it is R (float to two decimal places).<br>
I would like to write a python script which generates all possible combinations (Total of weighted averages) and print out only the one(s) which result in R. </p>

<p>How would I approach this problem?</p>

<p><strong>Example:</strong></p>

<p>N= 20 customers rated a product<br>
R = 3.85 is the average rating</p>

<p>Output I am looking for:</p>

<blockquote>
  <p>10 five-stars, 4 four-stars, 1 three-stars, 3 two-stars, and 2 one-star </p>
</blockquote>

<p>is one combination which would give 3.85 by 20 customers.</p>

<p>How would I test if there are any more combinations which could result in the given R and print them out as well? </p>

<p>The total number of stars is N*R (20 * 3.85 =  77 in your example).  Now what you have similar to <a href="https://en.wikipedia.org/wiki/Change-making_problem" rel="nofollow">the change making problem</a> except that your total number of coins is fixed.</p>

<p>An efficient solution might be to start with as many large coins (5 star ratings) as would not exceed the total, and decrease until you have ratings that would not make the total.  You still end up checking solutions that don't work, but it will be significantly faster than checking all solutions, especially for large problem sizes.</p>

<p>Here is my solution: (EDIT: Solution debugged.  I don't think its the optimal solution, but its better than brute force.  1931 recursive calls for the sample case of N=20 R=3.85)</p>

<pre><code>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 &lt; 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, [])
</code></pre>

python algorithm