将 N 项分配到一个集合中至少一次

Question

给定的是字典中的一组 N 个项目及其关联的出现。现在我必须根据每个项目的总体概率为每个项目准确分配 X 个插槽，但每个项目至少有 1 个插槽。

这是我想出的：

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 的转换在某个点截断了概率。

如何根据物品的数量将所有插槽至少映射一次？

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

Answer 2

之前的方法根据总计数分配剩余项目，而根据小数部分分配它们似乎更合理。例如，如果要分配最后一个槽位，则 0.8 的项目应该比 45.3 的项目（并且之前已经有 45 个槽位）得到最后一个槽位

我会：

用计算的整数部分初始化插槽并跟踪剩余的小数部分
然后将每个项目的小数部分按降序排列并分配，直到没有空位为止

示例实现如下所示：

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

将 N 项分配到一个集合中至少一次

Distribute N items over a Set at least once

c#

probability