將N個項目至少分配給一個集合

給定是詞典中的N個項目集合及其與其關聯的事件。現在，我必須根據其總概率爲每個項目分配完全X個插槽，但每個項目至少需要1個插槽。將N個項目至少分配給一個集合

這裏是我想出來的：

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

但是斷言觸發，從double到int轉換在某些點截斷的概率。

如何根據其數量將所有插槽至少映射一次到物品？

來源

2016-06-11 nonsensation

概率是一個分數，所以它應該是一個分數或乘以100來得到一個百分比。總數需要轉換爲double，因爲如果total是一個整數，c＃會將pair.value/total轉換爲整數。你真的希望pair.value/total是一個非整數。 – jdweng

Math.Ceiling（）也許？ – Master117

@jdweng爲什麼我需要一個百分比？此外，隨着我投一個操作數翻倍，概率已經是雙倍。 – nonsensation

以前的方法分配基礎上，TOTALCOUNT其餘的項目，而似乎更合理地根據自己的分數部分進行分配。例如，如果有指定的最後一個插槽，與0.8項而應獲得比45.3的項目最後一個插槽（並已經得到了45位前）

我想：

初始化與計算的integralpart插槽和跟蹤剩餘的小數部分
然後訂購每個項目的小數部分的降序排列併爲它們分配，直到沒有插槽處於

示例實現是這樣的：

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

來源

2016-06-11 15:51:36 Fabian

謝謝，這似乎是一個合理的方法 – nonsensation

由於時隙數量是一個整數，平均頻率不是 - 在初始空閒時隙分配後，您可能會留有空閒的時隙（如果將頻率降低）或者可能分配了比您真正擁有的更多時隙（如果您向上）。那麼合理的做法是：

首先根據頻率分配的所有插槽向下取整（那是你已經這樣做）
然後分配給左槽一個接一個地從最常見的項目開始（不能有更多的自由比項目總數還多的插槽）。

樣品實施：

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

來源

2016-06-11 15:45:37 Evk

將N個項目至少分配給一個集合

回答

相關問題