Problem to solve:
- Have a list of M products (eg 100000) with various prices.
- I want to randomly select n products(eg 10) that their sum of prices is S(eg. 100).
- Duplicates are allowed or not, does not matter.
Intrigued by a question on stackoverflow, I provided the following algorithm:
Considering the following:
In a collection of n positive numbers that sum up to S, at least one of them will be less than S divided by n (S/n).
Based on the above, you can break this down a set of steps:
- Select a product randomly where price < S/n. Get its price, lets say X.
- Select a product randomly where price < (S - X)/(n-1). Get its price, assume Y.
- Select a product randomly where price < (S - X - Y)/(n-2).
Repeat this (n-1) times and get (n-1) products. For the last product, select one where price = remaining price. (or order products by price descending with the condition of price <= remaining price and hopefully you could get close to the sum).
Alternatively, you could get (n-2) products and them find 2 products that sum to the remaining price to get better results.
Using code to construct the problem and run it, it produces a result set and also it appears fast.
- is the logic correct?
- is it random or is there a bias to it? Lets say we could produce all the different combinations of products that sum to S, will the above approach have equal possibility to produce any of the result sets?
- Can it be improved?
- Bonus: What is the cost? Its complexity in term of computations needed.
From a comment on the original question, the problem seem be equivalent to the knapsack problem where prices are the numbers and # products on each price is its weight.