将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
转换在某些点截断的概率。
如何根据其数量将所有插槽至少映射一次到物品?
答
以前的方法分配基础上,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;
}
+0
谢谢,这似乎是一个合理的方法 – 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;
}
概率是一个分数,所以它应该是一个分数或乘以100来得到一个百分比。总数需要转换为double,因为如果total是一个整数,c#会将pair.value/total转换为整数。你真的希望pair.value/total是一个非整数。 – jdweng
Math.Ceiling()也许? – Master117
@jdweng为什么我需要一个百分比?此外,随着我投一个操作数翻倍,概率已经是双倍。 – nonsensation