Распределите 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

предыдущий подход присваивает оставшиеся элементы, основанные на 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; 
} 

Answer 2

Поскольку количество слотов - это целое число, а средняя частота не равна - после первоначального бесплатного распределения слотов у вас могут быть свободные слоты влево (если вы округлите частоту вниз) или, возможно, назначили больше слотов, чем у вас на самом деле (если вы раунд вверх). Разумный подход, то есть:

1. Сначала распределить все слоты в соответствии с частотами округляется вниз (то есть то, что вы уже делаете)
2. Затем назначить левой пазами один за другим, начиная с наиболее часто пункта (не может быть больше свободного слоты слева, чем общее количество элементов).

Пример реализации:

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