Algorithm to distribute items "evenly"

Question

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways to describe it... later I'll provide a way to measure if a result is better than other).

So, for the list:

[1, 1, 2, 2, 3, 3]

One of the best results, after re-distributing the values, is:

[1, 2, 3, 1, 2, 3]

There may be other results as good as this one, and of course this gets more complicated with a less uniform set of values.

This is how to measure if a result is better than other:

1. Count the distances between each item and the next item with the same value.

2. Calculate the standard deviation for that set of distances. A lower dispersion means a better result.

Observations:

• When calculating a distance and the end of the list is reached without finding an item with the same value, we go back to the beginning of the list. So, at most, the same item will be found and the distance for that item will be the length of the list. This means that the list is cyclic;
• A typical list has ~50 items with ~15 different values in varied quantities.

So:

• For the result [1, 2, 3, 1, 2, 3], the distances are [3, 3, 3, 3, 3, 3], and the standard deviation is 0;
• For the result [1, 1, 2, 2, 3, 3], the distances are [1, 5, 1, 5, 1, 5], and the standard deviation is 2;
• Which makes the first result better than the second (lower deviation is better).

Given these definitions, I ask for a clue of which algorithms or strategies should I search for.

Answer 1

I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well.

If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you add all the A, then all the B, and then all the C. You're better off mixing smaller units. For example, do single-unit additions in the sequence [A,B,A,C,B,A]. That will prevent stratification altogether.

The way I found to do it is to treat it as a kind of merge, using a priority queue. If I create a structure to describe the additions:

MergeItem
    Item, Count, Frequency, Priority

The Frequency is expressed as "one every N". So A, which is added three out of six times, has a frequency of 2 (6/3).

And initialize a heap that initially contains:

(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

Now, I remove the first item from the heap and output it. Then reduce its count by 1 and increase Priority by Frequency and add it back to the heap. The resulting heap is:

(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

Next, remove B from the heap, output and update it, then add back to the heap:

(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

If I continue in that fashion, I get the desired mixture. I use a custom comparer to ensure that when equal Priority items are inserted into the heap, the one with the highest Frequency value (i.e. the least frequent) is ordered first.

I wrote a more complete description of the problem and its solution on my blog, and presented some working C# code that illustrates it. See Evenly distributing items in a list.

Update after comments

I do think my problem is similar to the OP's problem, and therefore that my solution is potentially useful. I apologize for not framing my answer more in the terms of the OP's question.

The first objection, that my solution is using A, B, and C rather than 0, 1, and 2, is easily remedied. It's simply a matter of nomenclature. I find it easier and less confusing to think about and say "two A's" rather than "two 1's". But for purposes of this discussion I have modified my outputs below to use the OP's nomenclature.

Of course my problem deals with the concept of distance. If you want to "spread things out evenly," distance is implied. But, again, it was my failing for not adequately showing how my problem is similar to the OP's problem.

I ran a few tests with the two examples that the OP provided. That is:

[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

In my nomenclature those are expressed as [2,2,2] and [4,3,2,1], respectively. That is, in the last example, "4 items of type 0, 3 items of type 1, 2 items of type 2, and 1 item of type 3."

I ran my test program (as described immediately below), and have posted my results. Absent input from the OP, I can't say if my results are similar to, worse than, or better than his. Nor can I compare my results to anybody else's results because nobody else has posted any.

I can say, however, that the algorithm provides a good solution to my problem of eliminating stratification when mixing liquids. And it looks like it provides a reasonable solution to the OP's problem.

For the results shown below, I used the algorithm that I detailed in my blog entry, with the initial priority set to Frequency/2, and the heap comparer modified to favor the more frequent item. The modified code is shown here, with the modified lines commented.

private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

Running my test program with the OP's first example, I get:

Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

So my algorithm works for the trivial problem of all counts being equal.

For the second problem that the OP posted, I got:

Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

I don't see an obvious way to improve on that. It could be rearranged to make the distances for item 0 [2,3,2,3] or some other arrangement of 2 and 3, but that will change the deviations for items 1 and/or 2. I really don't know what "optimum" is in this situation. Is it better to have a larger deviation on the more frequent or on the less frequent items?

Lacking other problems from the OP, I used his descriptions to make up a few of my own. He said in his post:

A typical list has ~50 items with ~15 different values in varied quantities.

So my two tests were:

[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

And my results:

Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

And for the second example:

Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0

Answer 2

This "smells" like it might be NP-hard. So, what do you do when you have a NP-hard problem? Throw a heuristic at it, or an approximation algorithm, or use a SAT solver.

In your case, if you don't need the absolute optimal solution, one reasonable starting point might be to try simulated annealing. There is a natural way to take any candidate solution and move it to a nearby candidate solution: randomly pick two items in the list, and swap them. Simulated annealing will iteratively try to improve the solution. You can find lots of resources on simulated annealing, if you're not familiar with it. You can also experiment with other sets of "local moves" that make small changes to a candidate solution, with the hopes of incrementally improving it (i.e., reducing the standard deviation of distances).

If that doesn't work out so well, my second suggestion would be to try throwing this at a SAT solver. Your problem sizes are small enough that this might just work. Start with the decision problem associated with your optimization function: given $t$, is there a solution whose standard deviation is $\le t$ (i.e., where the variance is $\le t^2$)? This can be expressed as a SAT instance. Expressing it as SAT will be messy, but if you use a front-end like STP, it will get a bit easier, as STP has support for integer arithmetic. So, you might have boolean unknowns $x_{i,j}$, where $x_{i,j}$ is true if the $i$th element of the array holds the value $j$. Now you can express some constraints that this is a valid permutation of the original input. You can also create some more integer unknowns and add constraints to force them to be equal to the distances between the elements, and then compute the variance of those distances and add a constraint asserting that it must be $\le t^2$. Of course, the worst-case running time of SAT solvers is exponential, so it's possible that SAT solvers might blow up on this problem... but it's also possible that they might be able to handle this problem. It's another technique you could try.

But I would suggest you start with simulated annealing. That's the first thing I would try, because I think it might just work.

Answer 3

Sketch of a heuristic algorithm

I have no exact solution for this problem. But since Raphael's comment suggests it looks like the partition problem, for which heuristic algorithms have been developed, I will try a heuristic approach. This is only a sketch of a heuristic algorithm.

Let $v$ be the number of values, and let $n$ be the number of elements in the list. We assume without loss of generality that the values are the numbers in $[1..n]$. For each value $i$ we note $n_i$ the number of its occurrences in the list.

We first note that the sum of the distances for all occurrences of a value is $n$. So the sum of all distances for all elements of the list is $vn$. Hence, the average distance for all elements of the list is $vn/n$, i.e., $v$.

Our purpose is to minimize the standard deviation on distances, which amounts to minimizing the sum of the squares of distance deviations, i.e. of differences between $v$ and each distance.

When placing the occurrences of one value, we try to equalize distances, up to integer constraints (and to the fact that slots may be occupied at some point). That is how they contribute the least to the standard deviation. If we are forced to increase a distance, it is always better to increase one that deviates the least. The the optimal distance for a value $i$ is $n/n_i$. Taking into account integer constraints, $n\mod n_i$ occurrences should use the integer value just above $n/n_i$, and the others just below.

That will guide our algorithm.

But first, we note that singleton values (occurring only once) will always have the same associated distance $n$. Hence their placement does not matter and can be ignored by the algorithm. They will just take whatever slots are left available at the end.

Then, since those distances that deviate most have to be the most exact to contribute less to the sum of squares, we try to place first the values that necessarily deviate most, i.e. the values $i$ such that $|n/n_i -v|$ is greatest.

It may be a value with very many of very few occurrences at first. I think it does not actually make a difference, since the constraints created by occupying slots are in proportion of the number of values well (?) placed.

Thr first value considered can be placed without any constraint. Then The other values must be placed so as to minimize their contribution to the standard deviation, but only in the slots left free by whatever values have been placed before.

The placement of the occurrences of a value in the remaining slots can be done with a dynamic programming algorithm, so as to merge computations that place the same number of values between two positions, keeping only those that have minimal contribution to the standard deviation (i.e. minimum value for the sum of the square of their deviations).

Occasionally, there will be several minimal solutions. In that case you try to preserve some slack by choosing the minimal solution that has the remaing slots most evenly distributed. THis can be computed, for each solution, by computing the standard deviation of the distances between the remaining free slots (with repect to their mean value, not with respect to $v$).

Then you repeat for the next remaining value $j$ such that $|n/n_j -v|$ is greatest, an so on until all non singleton values are placed.

Then you put the singleton values in the remaining slots.

I believe this should generally give reasonable solution, but I have yet no idea on how to prove it or estimate the gap with an optimal solution.

Answer 4

It looks like I'm very late to the party, but posting in case anyone runs into this again. My solution is similar to @babou's plus. Earlier today, I had a scheduling problem in an embedded system which led me to this thread. I have an implementation specific to my problem in C, but I figured I'd post a more generic solution in Python here (the C version is complicated by the fact that I've restricted myself to a small, fixed size stack and no memory allocations, so I perform the whole algorithm in-place). The anti-aliasing technique used below is something you might use for drawing a line on a screen with 2 bit colour. The algorithm here achieves a lower score (i.e., better) when measured using the sum of standard deviation for the inputs used by Jim Mischel than that particular solution. Run-time for this implementation (assuming a good sorting algorithm): O(m*n) where m is the number of types of items and n is the total number of items to distribute.

def generate(item_counts):
'''item_counts is a list of counts of "types" of items. E.g., [3, 1, 0, 2] represents
   a list containing [1, 1, 1, 2, 4, 4] (3 types of items/distinct values). Generate
   a new list with evenly spaced values.'''
# Sort number of occurrences by decreasing value.
item_counts.sort(reverse=True)
# Count the total elements in the final list.
unplaced = sum(item_counts)
# Create the final list.
placements = [None] * unplaced

# For each type of item, place it into the list item_count times.
for item_type, item_count in enumerate(item_counts):
    # The number of times the item has already been placed
    instance = 0
    # Evenly divide the item amongst the remaining unused spaces, starting with
    # the first unused space encountered.
    # blank_count is the number of unused spaces seen so far and is reset for each
    # item type.
    blank_count = -1
    for position in range(len(placements)):
        if placements[position] is None:
            blank_count += 1
            # Use an anti-aliasing technique to prevent bunching of values.
            if blank_count * item_count // unplaced == instance:
                placements[position] = item_type
                instance += 1
    # Update the count of number of unplaced items.
    unplaced -= item_count

return placements

Results for

Input counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sum of stddev: 16.8 (vs. 22.3 via Jim Mischel)

Input of counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sum of stddev: 18.0 (vs. 19.3 via Jim Mischel)

If given inputs of the form specified by @moraes, one can convert it to a form usable by this function in O(n) steps using Big Omega(n * log(n)) bits of memory where n is the number of items (in a list with 255 elements, you won't need more than 255 extra bytes) by keeping a parallel array with the repetition counts. Alternately, one can perform a pair of in-place sorts with O(1) extra memory.

P.S.

import numpy
import collections

def evaluate(l):
    '''Given a distribution solution, print the sum of stddevs for each type in the solution.'''
    l2 = l * 2
    distances = [None] * len(l)
    distance_dict = collections.defaultdict(list)
    for i in range(len(l)):
        distances[i] = l2.index(l[i], i + 1) - i
        distance_dict[l[i]].append(l2.index(l[i], i + 1) - i)

    keys = list(distance_dict.keys())
    keys.sort()
    score = 0
    # Calculate standard deviations for individual types.
    for key in keys:
        sc = numpy.std(distance_dict[key])
        score += sc
    print('Stddev sum: ', score)

Edit: I know this solution does not produce the optimal output by counterexample. An input of [6, 2, 1] produces [0, 1, 0, 0, 2, 0, 0, 1, 0]; a better solution is [0, 0, 1, 0, 2, 0, 0, 1, 0].

Answer 5

This algorithm works with an array of integers, where each integer represents a different category. It creates separate arrays for each category. For example, if the starting array is [1, 1, 1, 2, 2, 3], it will create three arrays, [3], [2, 2], [1, 1, 1].

From there it recursively combines the two smallest arrays (in this example, the [3], and [2,2]) and spaces the placement of the elements of the smaller array into the second smallest array based mostly on the ratio of the number of occurrences of the larger vs the smaller categories. In this example, we would wind up with [2,3,2]. Then it would use this array as the smaller array that will be combined into the next larger array, until there is only one array left.

<?php
/**
 *This will separete the source array into separate arrays for each category
 */
function splitArrayByCategory($source) {

    //  index is the category, value is the tally
    $categoryCounts  = array_count_values($source);

    // Sort that list, keep index associations
    asort($categoryCounts);

    // build separate arrays for each category
    // index = order, smaller index = smaller category count
    // value = array of each category
    $separated = array();
    foreach ($categoryCounts as $category => $tally)
        $separated[] = array_fill(0, $tally, $category);

    return $separated;
}

/**
 * Will take the array of arrays generated by splitArrayByCategory, and merge
 * them together so categories are evenly distributed
 */
function mergeCategoryArrays($categoryArray) {

    // How many entries are there, for the smallest & second smallest categories
    $smallerCount = count($categoryArray[0]);
    $largerCount  = count($categoryArray[1]);

    // Used to determine how much space there should be between these two categories
    $space = $largerCount/$smallerCount;

    // Merge the array of the smallest category into the array of the second smallest
    foreach ($categoryArray[0] as $domIndex => $domain) {
        // Where should we splice the value into the second array?
        $location = floor($domIndex*$space+$domIndex+($space/2));
        // actually perform the splice
        array_splice($categoryArray[1], $location, 0, $domain);
    }

    // remove the smallest domain we just spliced into the second smallest
    unset($categoryArray[0]);

    // reset the indexes
    $categoryArray = array_values($categoryArray);

    // If we have more than one index left in the categoryArray (i.e. some things
    // still need to get merged), let's re-run this function,
    if (count($categoryArray)>1)
        $categoryArray = mergeCategoryArrays($categoryArray);

    return $categoryArray;
}

// The sample list we're working with.
// each integer represents a different category
$listSample = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,6,6,7,7,7,7];

// Split the sample list into separate arrays for each category
$listSplitByCategory = splitArrayByCategory($listSample);

// If there are not at least two categories, what's the point?
if (count($listSplitByCategory) < 2) throw new Exception("You need at least two categories");

// perform the actual distribution of categories.
$listEvenlyDistributed = mergeCategoryArrays($listSplitByCategory)[0];

// Display the array before and after the categories are evenly distributed
for ($i=0; $i<count($listSample); $i++) {
    print $listSample[$i].",";
    print $listEvenlyDistributed[$i]."\n";
}

Answer 6

ANSI C CODE

This code works by imagining a straight line in n dimensional space (where n is the number of categories) passing through the origin with directional vector (v1, v2, ..., vi, ... vn) where vi is the number of items in category i. Starting from the origin the aim is to find the next nearest point to the line. Using the example [0 0 0 0 0 1 1 1 2 2 2 3] it produces the result [0 1 2 0 3 1 0 2 0 1 2 0]. Using Lungj's example [0 0 0 0 0 0 1 1 2] we get [0 1 0 0 2 0 0 1 0], which is exactly the same as Lungj's result.

The algorithm is made more efficient by only using integer arithmetic and considering only the deltas between the distances from each point to the line.

#define MAXCATEGORIES 100

int main() { int i = 0; int j = 0; int catsize = 0; int vector[MAXCATEGORIES]; int point[MAXCATEGORIES]; int categories = 0; int totalitems = 0; int best = 0; long d2 = 0L; long vp = 0L; long v2 = 0L; long delta = 0L; long beta = 0L;

printf("Enter the size of each category (enter 0 to finish):\r\n");
do
{
    catsize = 0;
    #ifdef _MSVC_LANG
            scanf_s("%d", &catsize);
    #else
            scanf("%d", &catsize)
    #endif
    if (catsize > 0)
    {
        vector[categories] = catsize;
        totalitems += catsize;
        categories++;
    }
} while (catsize > 0);

for (i = 0; i < categories; i++)
{
    v2 += vector[i] * vector[i];
    point[i] = 0;
}

for (i = 0; i < totalitems; i++)
{
    for (j = 0; j < categories; j++)
    {
        delta = (2 * point[j] + 1)*v2 - (2 * vp + vector[j])*vector[j];
        if (j == 0 || delta < beta)
        {
            best = j;
            beta = delta;
        }
    }
    point[best]++;
    vp += vector[best];
    printf("%c ", best + '0');  // Change '0' to 'A' if you like letters instead
}
return 0;

}

Answer 7

my solution:

    vc = train['classes'].value_counts()
    vc = dict(sorted(vc.items()))
    df = pd.DataFrame()
    train['col_for_sort'] = 0.0

    i=1
    for k,v in vc.items():
        step = train.shape[0]/v
        indent = train.shape[0]/(v+1)
        df2 = train[train['classes'] == k].reset_index(drop=True)
        for j in range(0, v):
        df2.at[j, 'col_for_sort'] = indent + j*step + 0.0001*i   
    df= pd.concat([df2,df])
    i+=1

    train = df.sort_values('col_for_sort', ascending=False).reset_index(drop=True)
    del train['col_for_sort']