将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个项目至少分配给一个集合

回答

相关问题