c# - Distribute N items over a Set at least once -

given set of n items in dictionary , occurrences associated it. have assign x slots each item based on overall probability, @ least 1 slot per item.

here i've come with:

using system.collections.generic; using system.diagnostics; using system.linq;  public static class program {     public static void main( string[] args )     {         var dict = new dictionary<char,int>();          dict.add( 'a' , 10 );   dict.add( 'b' , 0 );         dict.add( 'c' , 4 );    dict.add( 'd' , 1 );         dict.add( 'e' , 9 );    dict.add( 'f' , 0 );          var distributionmap = distribute( dict , 40 );     }      public static dictionary<t,int> distribute<t>( dictionary<t,int> occurmap , int slots )     {         var freeslots = slots - occurmap.count;         var total = occurmap.sum( x => x.value );         var distmap = new dictionary<t,int>();          foreach( var pair in occurmap )         {             var probability = (double)pair.value / total;             var assignedslots = probability * freeslots;              distmap[ pair.key ] = (int)( 1 + assignedslots );         }          debug.assert( distmap.select( x => x.value ).sum() == slots );          return distmap;     } } 

however assert triggers, conversion double int truncates probability @ point.

how map slot @ least once items based on count?

the previous approach assigns remaining items based on totalcount whereas seems more reasonable assign them based on fractional part. example if there 1 last slot assign, item 0.8 should rather last slot item 45.3 (and got 45 slots before)

i would:

• initialize slots integralpart of computation , keep track of remaining fractional parts
• then order fractional parts each item in descending order , assign them until no slots left

a sample implementation this:

public static dictionary<t,int> distribute<t>( dictionary<t,int> occurmap , int slots ) {     var freeslots = slots -  occurmap.count;     var totalfreeslots = freeslots;     var total = occurmap.sum( x => x.value );     var distmap = new dictionary<t,int>();     var remainingslots = new dictionary<t,double>();      foreach( var pair in occurmap )     {         var probability = (double)pair.value / total;         var assignedslots = probability * totalfreeslots;          var integralpart = math.truncate(assignedslots);         var fractionalpart = assignedslots - integralpart;                              distmap[ pair.key ] = 1 + (int)integralpart;         remainingslots[pair.key] = fractionalpart;         freeslots -= (int)integralpart;     }         foreach (var pair in remainingslots.tolist().orderbydescending(x => x.value))     {         if (freeslots == 0)             break;          distmap[ pair.key ]++;         freeslots -= 1;     }                   return distmap; }