I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.
Here is the problem :
Consider a list of M sets that ( M = 10000 )
- each set contains integers in range 1... N. (Let's say N=50)
- each set has the size of K. ( Let's say K=10)
- each element in the set is distinct.
Sample sets are
- { 1,2,3,4,5,6,7,8,9,10}
- { 2,4,5,7,9,11,13,15,20,25}
- { 4,5,8,12,16,30,41,42,45,49}
- { 2,6,11,18,24,27,31,36,39,43}
....
- { 3,5,8,17,19,23,34,37,38,46 }
You should select L sets(Let's say L=1000) from given 10000 sets. This selection must approximately satisfy a distribution table like below
- 1=> 100 %
- 2=> 80 %
- 3=> 100 %
- 4=> 15 %
...
- 50=> 20%
It means that 1 should occur in all selections, 2 should occur 80% of the selections and goes on ... I will try to solve the problem by trying a random-walk algorithm that exchanges a set in each iteration.
I'm sorry if I did not express my problem well. It would be great if you could share similar problems with mine or could express your approach to the problem.