如何平均分配项目，没有随机数

Question

我有一种情况，我需要在M个插槽间平均分配N个项目。每个项目都有自己的分配％。为了讨论的目的，假设有三个项目（a，b，c），其中各个百分比（50,25,25）均匀分布在20个时隙中。因此需要分配10 X a，5 X b & 5 X c。其结果将是如下：

1. a 
2. a 
3. c 
4. b 
5. a 
6. a 
7. c 
8. b 
9. a 
10. a 
11. c 
12. b 
13. a 
14. a 
15. c 
16. b 
17. a 
18. a 
19. c 
20. b 

，我挣扎的部分是槽的数量，项目和百分比数都可以改变，当然百分比总是合计达100％。我写的代码导致后面的输出，它总是被重新加权，以支持具有最高百分比的项目。任何想法都会很棒。

1. a 
2. b 
3. c 
4. a 
5. b 
6. c 
7. a 
8. b 
9. c 
10. a 
11. c 
12. b 
13. a 
14. b 
15. c 
16. a 
17. a 
18. a 
19. a 
20. a 

编辑 这是我的代码目前的模样。正如我前面提到的那样，反向加权分配结果。对于一个小环境，我试图平均分配广告节目。因此，每次使用相同输入的运行必须得到完全相同的输出。这就是排除使用随机数的原因。

foreach (ListRecord spl in lstRecords){ 

    string key = spl.AdvertiserName + spl.ContractNumber + spl.AgencyAssignmentCode; 

    if (!dictCodesheets.ContainsKey(key)){ 

     int maxAssignmentForCurrentContract = weeklyList.Count(c => (c.AdvertiserName == spl.AdvertiserName) && (c.AgencyAssignmentCode == spl.AgencyAssignmentCode) 
               && (c.ContractNumber == spl.ContractNumber) && (c.WeekOf == spl.WeekOf)); 


     int tmpAssignmentCount = 0; 

     for (int i = 0; i < tmpLstGridData.Count; i++) 
     { 
      GridData gData = tmpLstGridData[i]; 

      RotationCalculation commIDRotationCalc = new RotationCalculation(); 
      commIDRotationCalc.commercialID = gData.commercialID; 

      commIDRotationCalc.maxAllowed = (int)Math.Round(((double)(maxAssignmentForCurrentContract * gData.rotationPercentage)/100), MidpointRounding.AwayFromZero); 
      tmpAssignmentCount += commIDRotationCalc.maxAllowed; 

      if (tmpAssignmentCount > maxAssignmentForCurrentContract) 
      { 
       commIDRotationCalc.maxAllowed -= 1; 
      } 


      if (i == 0) 
      { 
       commIDRotationCalc.maxAllowed -= 1; 
       gridData = gData; 
      } 

      commIDRotationCalc.frequency = (int)Math.Round((double)(100/gData.rotationPercentage)); 

      if (i == 1) 
      { 
       commIDRotationCalc.isNextToBeAssigned = true; 
      } 

      lstCommIDRotCalc.Add(commIDRotationCalc); 
     } 

     dictCodesheets.Add(key, lstCommIDRotCalc); 

    }else{ 

      List<RotationCalculation> lstRotCalc = dictCodesheets[key]; 

      for (int i = 0; i < lstRotCalc.Count; i++) 
      { 

       if (lstRotCalc[i].isNextToBeAssigned) 
       { 
        gridData = tmpLstGridData.Where(c => c.commercialID == lstRotCalc[i].commercialID).FirstOrDefault(); 
        lstRotCalc[i].maxAllowed -= 1; 

        if (lstRotCalc.Count != 1) 
        { 
         if (i == lstRotCalc.Count - 1 && lstRotCalc[0].maxAllowed > 0) 
         { 
          //Debug.Print("In IF"); 
          lstRotCalc[0].isNextToBeAssigned = true; 
          lstRotCalc[i].isNextToBeAssigned = false; 

          if (lstRotCalc[i].maxAllowed == 0) 
          { 
           lstRotCalc.RemoveAt(i); 
          } 

          break; 
         } 
         else 
         { 
          if (lstRotCalc[i + 1].maxAllowed > 0) 
          { 
           //Debug.Print("In ELSE"); 
           lstRotCalc[i + 1].isNextToBeAssigned = true; 
           lstRotCalc[i].isNextToBeAssigned = false; 

           if (lstRotCalc[i].maxAllowed == 0) 
           { 
            lstRotCalc.RemoveAt(i); 
           } 

           break; 
          } 
         } 
        } 

       } 
      } 

     } 

} 

编辑2 想在这里澄清我的要求。目前，由于项目'a'将被分配10次，这是所有三个项目中最高的，在分配结束时，项目16-20全部只被分配了'a'。正如评论中提到的那样，我试图实现更“均匀”的分配。

Answer 1

这里是一个没有随机数，让所需的输出。

using System; 
using System.Collections.Generic; 

public class Program 
{ 
    public static void Main() 
    { 
     // name, percentage 
     Dictionary<string, double> distribution = new Dictionary<string,double>(); 

     // name, amount if one more were to be distributed 
     Dictionary<string, int> dishedOut = new Dictionary<string, int>(); 

     //Initialize 
     int numToGive = 20; 
     distribution.Add("a", 0.50); 
     distribution.Add("b", 0.25); 
     distribution.Add("c", 0.25); 

     foreach (string name in distribution.Keys) 
      dishedOut.Add(name, 1); 

     for (int i = 0; i < numToGive; i++) 
     { 
      //find the type with the lowest weighted distribution 
      string nextUp = null; 
      double lowestRatio = double.MaxValue; 
      foreach (string name in distribution.Keys) 
       if (dishedOut[name]/distribution[name] < lowestRatio) 
       { 
        lowestRatio = dishedOut[name]/distribution[name]; 
        nextUp = name; 
       } 

      //distribute it 
      dishedOut[nextUp] += 1; 
      Console.WriteLine(nextUp); 
     } 

     Console.ReadLine(); 
    } 
} 

Answer 2

//AABC AABC…    
int totalA = 10   
int totalB = 5   
int totalC = 5   
int totalItems = 20 //A+B+C   

double frequencyA = totalA/totalItems; //0.5   
double frequencyB = totalB/totalItems; //0.25   
double frequencyC = totalC/totalItems; //0.25   

double filledA = frequencyA;    
double filledB = frequencyB;    
double filledC = frequencyC;    

string output = String.Empty;   

while(output.Length < totalItems) 
{  
    filledA += frequencyA;  
    filledB += frequencyB;  
    filledC += frequencyC;  

    if(filledA >= 1) 
    {  
     filledA -= 1; 
     output += "A"; 
     if(output.Length == totalItems){break;} 
    } 
    if(filledB >= 1)  
    { 
     filledB -= 1  
     output += "B"; 
     if(output.Length == totalItems){break;} 
    } 
    if(filledC >= 1)   
    { 
     filledC -= 1  
     output += "C"; 
     if(output.Length == totalItems){break;} 
    } 
} 

Answer 3

这个答案大多是偷来的，轻轻适合您的使用从here

我的想法是，你可以在无需护理为了最简单的方式分发您的项目，然后改组列表。

public static void ShuffleTheSameWay<T>(this IList<T> list) 
{ 
    Random rng = new Random(0); 
    int n = list.Count; 
    while (n > 1) { 
     n--; 
     int k = rng.Next(n + 1); 
     T value = list[k]; 
     list[k] = list[n]; 
     list[n] = value; 
    } 
} 

小提琴here

Answer 4

而是一个真正的随机数生成器，使用固定的种子，使方案具有每次运行它（对于相同的输入）时相同的输出。在下面的代码中，'0'是种子，这意味着每次程序运行时生成的'随机'数字总是相同的。

Random r = new Random(0); 

Answer 5

查看此问题的一种方法是作为多维线条绘制问题。所以我使用Bresenham的线算法来创建分布：

public static IEnumerable<T> GetDistribution<T>(IEnumerable<Tuple<T, int>> itemCounts) 
{ 
    var groupCounts = itemCounts.GroupBy(pair => pair.Item1) 
           .Select(g => new { Item = g.Key, Count = g.Sum(pair => pair.Item2) }) 
           .OrderByDescending(g => g.Count) 
           .ToList(); 

    int maxCount = groupCounts[0].Count; 
    var errorValues = new int[groupCounts.Count]; 

    for(int i = 1; i < errorValues.Length; ++i) 
    { 
     var item = groupCounts[i]; 
     errorValues[i] = 2 * groupCounts[i].Count - maxCount; 
    } 

    for(int i = 0; i < maxCount; ++i) 
    { 
     yield return groupCounts[0].Item; 

     for(int j = 1; j < errorValues.Length; ++j) 
     { 
      if(errorValues[j] > 0) 
      { 
       yield return groupCounts[j].Item; 
       errorValues[j] -= 2 * maxCount; 
      } 

      errorValues[j] += 2 * groupCounts[j].Count; 
     } 
    } 
} 

输入是您想要的每个项目的实际数量。这有几个好处。首先它可以使用整数算术，避免任何舍入问题。如果您要求10个项目并且要求3个项目均匀分布（这基本上只是再次舍入问题），它也会摆脱任何歧义。