如何平均分配項目，沒有隨機數

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個項目均勻分佈（這基本上只是再次舍入問題），它也會擺脫任何歧義。