How to distribute items evenly, without random numbers

Question

I have a situation where I need to evenly distribute N items across M slots. Each item has its own distribution %. For discussion purposes say there are three items (a,b,c) with respective percentages of (50,25,25) to be distributed evenly across 20 slots. Hence 10 X a,5 X b & 5 X c need to be distributed. The outcome would be as follows:

 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

The part that I am struggling with is that the number of slots, number of items and percentages can all vary, of course the percentage would always total up to 100%. The code that I wrote resulted in following output, which is always back weighted in favour of item with highest percentage. Any ideas would be great.

 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

Edit This is what my code currently looks like. Results in back weighted distribution as I mentioned earlier. For a little context, I am trying to evenly assign commercials across programs. Hence every run with same inputs has to result in exactly the same output. This is what rules out the use of random numbers.

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

                }
            }

        }

}

Edit 2 Trying to clear up my requirement here. Currently, because item 'a' is to be assigned 10 times which is the highest among all three items, towards the end of distribution, items 16 - 20 all have been assigned only 'a'. As has been asked in comments, I am trying to achieve a distribution that "looks" more even.

Answer 1

One way to look at this problem is as a multi-dimensional line drawing problem. So I used Bresenham's line algorithm to create the distribution:

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

The input is the actual number of each item you want. This has a couple advantages. First it can use integer arithmetic, which avoids any rounding issues. Also it gets rid of any ambiguity if you ask for 10 items and want 3 items evenly distributed (which is basically just the rounding issue again).

Answer 2

Here's one with no random number that gives the required output.

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 3

//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 4

This answer was mostly stolen and lightly adapted for your use from here

My idea is that you distribute your items in the simplest way possible without care of order, then shuffle the list.

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

Fiddle here

Answer 5

Instead of a truly random number generator, use a fixed seed, so that the program has the same output every time you run it (for the same input). In the code below, the '0' is the seed, which means the 'random' numbers generated will always be the same each time the program is run.

 Random r = new Random(0);