N個のアイテムを少なくとも1回セットに配付

Question

Givenは、辞書内のN個のアイテムのセットとそれに関連するオカレンスです。 今度は、アイテムごとに1つのスロット以上の、全体的な確率に基づいて、各アイテムに正確にXスロットを割り当てる必要があります。 doubleからintへの変換は、いくつかの点で確率を切り捨てとしてアサートは、トリガーしかし

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; 
    } 
} 

：ここ

は、私が作ってみたものです。

は、どのように私は彼らの数に基づいてアイテムに少なくとも一度はすべてのスロットをマッピングしていますか？

Answer 1

以前のアプローチは、彼らの小数部に基づいて割り当てることがより合理的と思われる一方、トータルカウントに基づいて、残りの項目を割り当てます。希望Iは、例えば、割り当てる最後のスロットが存在する場合、0.8との項目はなく45.3とアイテムより最後のスロットを取得する必要があり（それは既に前に45個のスロットを持っ）

：

• 初期化スロット計算integralpart有するとNOスロットが

を残さなくなるまでサンプルの実装は次のようになり降順に各項目の小数部分を注文し、それらを割り当て、残りの小数部分

を追跡：

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; 
} 

Answer 2

スロットの数は、全体の数であり、平均周波数ではないので - 最初の空きスロット配布した後は、空きスロットが残っている場合があります（もしあなたラウンド周波数ダウン）かもしラウンド（あなたが本当に持っているよりも多くのスロットが割り当てられている場合がありますアップ）。合理的なアプローチは次のようになります。まず、周波数に応じてすべてのスロットを

1. 配布
2. （それはあなたがすでに何をすべきかです）切り捨て次に（もっと自由があることはできません左のスロットに最も頻出アイテムから1つずつ割り当てますスロットはアイテムの総数よりも残っています）。

サンプルインプリメンテーション：

public static Dictionary<T, int> Distribute<T>(Dictionary<T, int> occurMap, int slots) 
{ 
    if(slots < occurMap.Count) 
     throw new ArgumentException("Not enough slots"); 

    var freeSlots = slots - occurMap.Count; 
    var total = occurMap.Sum(x => x.Value); 
    var distMap = new Dictionary<T, int>(); 
    var keysByProb = new Queue<T>(); 
    foreach (var pair in occurMap.OrderByDescending(c => (double)c.Value/total)) 
    { 
     var probability = (double)pair.Value/total; 
     var assignedSlots = probability * freeSlots; 

     distMap[pair.Key] = 1+ (int)Math.Floor(assignedSlots); 
     keysByProb.Enqueue(pair.Key); 
    } 
    var left = slots - distMap.Select(x => x.Value).Sum(); 
    while (left > 0) { 
     distMap[keysByProb.Dequeue()]++; 
     left--; 
    } 
    Debug.Assert(distMap.Select(x => x.Value).Sum() == slots); 
    return distMap; 
}