Estou procurando um algoritmo para distribuir valores de uma lista para que a lista resultante seja o mais "equilibrada" ou "distribuída uniformemente" quanto possível (entre aspas, porque não tenho certeza de que essas são as melhores maneiras de descrevê-la ... mais tarde, fornecerei uma maneira de medir se um resultado é melhor que outro).

Então, para a lista:

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

Um dos melhores resultados, após a redistribuição dos valores, é:

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

Pode haver outros resultados tão bons quanto este e, é claro, isso fica mais complicado com um conjunto de valores menos uniforme.

É assim que se mede se um resultado é melhor que outro:

1. Conte as distâncias entre cada item e o próximo item com o mesmo valor.

2. Calcule o desvio padrão para esse conjunto de distâncias. Uma menor dispersão significa um resultado melhor.

Observações:

• Ao calcular uma distância e chegar ao fim da lista sem encontrar um item com o mesmo valor, voltamos ao início da lista. Portanto, no máximo, o mesmo item será encontrado e a distância para esse item será o comprimento da lista. Isso significa que a lista é cíclica ;
• Uma lista típica possui ~ 50 itens com ~ 15 valores diferentes em quantidades variadas.

Tão:

• Para o resultado [1, 2, 3, 1, 2, 3], as distâncias são [3, 3, 3, 3, 3, 3]e o desvio padrão é 0;
• Para o resultado [1, 1, 2, 2, 3, 3], as distâncias são [1, 5, 1, 5, 1, 5]e o desvio padrão é 2;
• O que torna o primeiro resultado melhor que o segundo (o desvio menor é melhor).

Dadas essas definições, peço uma pista de quais algoritmos ou estratégias devo procurar.

Eu me deparei com essa pergunta enquanto pesquisava um problema semelhante: adições ótimas de líquidos para reduzir a estratificação. Parece que minha solução também seria aplicável à sua situação.

Se você deseja misturar os líquidos A, B e C na proporção 30,20,10 (ou seja, 30 unidades de A, 20 unidades de B e 10 unidades de C), você terminará com estratificação se adicionar todos os o A, depois todo o B e depois todo o C. É melhor misturar unidades menores. Por exemplo, faça adições de unidade única na sequência [A, B, A, C, B, A]. Isso impedirá completamente a estratificação.

A maneira que encontrei para fazer isso é tratá-lo como uma espécie de mesclagem, usando uma fila de prioridade. Se eu criar uma estrutura para descrever as adições:

MergeItem
    Item, Count, Frequency, Priority

A frequência é expressa como "um a cada N". Então A, que é adicionado três em seis vezes, tem uma frequência de 2 (6/3).

E inicialize um heap que contém inicialmente:

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

Agora, removo o primeiro item da pilha e o produzo. Em seguida, reduza sua contagem em 1 e aumente a Prioridade por frequência e adicione-a novamente ao heap. O heap resultante é:

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

Em seguida, remova B do heap, produza e atualize-o e adicione-o novamente ao heap:

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

Se eu continuar dessa maneira, recebo a mistura desejada. Uso um comparador personalizado para garantir que, quando itens de prioridade igual forem inseridos no heap, aquele com o maior valor de frequência (ou seja, o menos frequente) seja solicitado primeiro.

Eu escrevi uma descrição mais completa do problema e sua solução no meu blog e apresentei alguns códigos C # funcionais que ilustram isso. Consulte Distribuição uniforme de itens em uma lista .

Atualizar após comentários

Acho que meu problema é semelhante ao do OP e, portanto, que minha solução é potencialmente útil. Peço desculpas por não enquadrar minha resposta mais nos termos da pergunta do OP.

A primeira objeção, de que minha solução está usando A, B e C, em vez de 0, 1 e 2, é facilmente remediada. É simplesmente uma questão de nomenclatura. Acho mais fácil e menos confuso pensar e dizer "dois A's" em vez de "dois 1's". Mas, para os propósitos desta discussão, modifiquei minhas saídas abaixo para usar a nomenclatura do OP.

É claro que meu problema lida com o conceito de distância. Se você deseja "espalhar as coisas uniformemente", a distância está implícita. Mas, novamente, foi minha falha por não mostrar adequadamente como meu problema é semelhante ao problema do OP.

Fiz alguns testes com os dois exemplos que o OP forneceu. Isso é:

[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]

Na minha nomenclatura, esses são expressos como [2,2,2] e [4,3,2,1], respectivamente. Ou seja, no último exemplo, "4 itens do tipo 0, 3 itens do tipo 1, 2 itens do tipo 2 e 1 item do tipo 3."

Eu executei meu programa de teste (como descrito imediatamente abaixo) e publiquei meus resultados. Ausência de informações do OP, não sei dizer se meus resultados são semelhantes a, piores ou melhores que os dele. Nem posso comparar meus resultados com os resultados de mais ninguém porque ninguém mais postou nenhum.

Posso dizer, no entanto, que o algoritmo fornece uma boa solução para o meu problema de eliminar a estratificação ao misturar líquidos. E parece que fornece uma solução razoável para o problema do OP.

Para os resultados mostrados abaixo, usei o algoritmo que detalhei na entrada do meu blog, com a prioridade inicial definida como Frequency/2e o comparador de heap modificado para favorecer o item mais frequente. O código modificado é mostrado aqui, com as linhas modificadas comentadas.

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

Executando meu programa de teste com o primeiro exemplo do OP, recebo:

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

Portanto, meu algoritmo funciona para o problema trivial de todas as contagens serem iguais.

Para o segundo problema que o OP postou, obtive:

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

Não vejo uma maneira óbvia de melhorar isso. Poderia ser reorganizado para fazer as distâncias para o item 0 [2,3,2,3] ou algum outro arranjo de 2 e 3, mas isso mudará os desvios para os itens 1 e / ou 2. Eu realmente não sei o que "ótimo" está nessa situação. É melhor ter um desvio maior nos itens mais frequentes ou nos menos frequentes?

Na falta de outros problemas do OP, usei suas descrições para fazer algumas das minhas. Ele disse em seu post:

Uma lista típica possui ~ 50 itens com ~ 15 valores diferentes em quantidades variadas.

Então, meus dois testes foram:

[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

E meus resultados:

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

E para o segundo exemplo:

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

Isso "cheira" como se fosse NP-difícil. Então, o que você faz quando tem um problema NP-hard? Lance uma heurística, ou um algoritmo de aproximação, ou use um solucionador SAT.

No seu caso, se você não precisar da solução ótima absoluta, um ponto de partida razoável pode ser tentar o recozimento simulado . Existe uma maneira natural de pegar qualquer solução candidata e movê-la para uma solução candidata próxima: escolha aleatoriamente dois itens da lista e troque-os. O recozimento simulado tentará iterativamente melhorar a solução. Você pode encontrar muitos recursos no recozimento simulado, se não estiver familiarizado. Você também pode experimentar outros conjuntos de "movimentos locais" que fazem pequenas alterações em uma solução candidata, com a esperança de melhorá-la de forma incremental (isto é, reduzir o desvio padrão das distâncias).

$t$$\le t$$\le t^2$$x_{i,j}$$x_{i,j}$$i$$j$$\le t^2$

Mas eu sugiro que você comece com um recozimento simulado. Essa é a primeira coisa que eu tentaria, porque acho que poderia funcionar.

Esboço de um algoritmo heurístico

Não tenho uma solução exata para esse problema. Mas como o comentário de Raphael sugere que ele se parece com o problema de partição, para o qual os algoritmos heurísticos foram desenvolvidos, tentarei uma abordagem heurística. Este é apenas um esboço de um algoritmo heurístico.

$v$$n$$[1..n]$$i$$n_i$

$n$$vn$$vn/n$$v$

$v$

$i$$n/n_i$$n\mod n_i$$n/n_i$

Isso guiará nosso algoritmo.

$n$

$i$$|n/n_i -v|$

Pode ser um valor com muitas poucas ocorrências no início. Eu acho que realmente não faz diferença, uma vez que as restrições criadas pela ocupação de slots são na proporção do número de valores bem colocados (?).

O primeiro valor considerado pode ser colocado sem qualquer restrição. Os outros valores devem ser colocados de modo a minimizar sua contribuição para o desvio padrão, mas apenas nos slots deixados livres por quaisquer valores que tenham sido colocados anteriormente.

A colocação das ocorrências de um valor nos slots restantes pode ser feita com um algoritmo de programação dinâmica, de modo a mesclar cálculos que colocam o mesmo número de valores entre duas posições, mantendo apenas aqueles que têm contribuição mínima para o desvio padrão (ou seja, valor mínimo para a soma do quadrado de seus desvios).

$v$

Em seguida, repita para o próximo valor restante $j$$|n/n_j -v|$

Em seguida, você coloca os valores singleton nos slots restantes.

Acredito que isso geralmente deva dar uma solução razoável, mas ainda não tenho idéia de como provar ou estimar a lacuna com uma solução ideal.

Parece que estou muito atrasado para a festa, mas postando caso alguém se depare com isso novamente. Minha solução é semelhante à @ babou's plus. Hoje cedo, tive um problema de agendamento em um sistema incorporado que me levou a esse segmento. Eu tenho uma implementação específica para o meu problema em C, mas achei que postaria uma solução mais genérica em Python aqui (a versão C é complicada pelo fato de me restringir a uma pilha pequena e de tamanho fixo e sem memória alocações, então eu executo todo o algoritmo no local). A técnica de suavização de serrilhado usada abaixo é algo que você pode usar para desenhar uma linha em uma tela com cores de 2 bits. O algoritmo aqui obtém uma pontuação mais baixa (ou seja, melhor) quando medido usando a soma do desvio padrão para as entradas usadas por Jim Mischel do que essa solução específica.

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

Resultados para

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)

Se forem fornecidas entradas do formulário especificado por @moraes, pode-se convertê-lo em um formulário utilizável por esta função em O (n) etapas usando Big Omega (n * log (n)) bits de memória em que n é o número de itens ( em uma lista com 255 elementos, você não precisará de mais de 255 bytes extras) mantendo uma matriz paralela com a contagem de repetições. Como alternativa, é possível executar um par de classificações no local com memória extra O (1).

PS

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: Eu sei que esta solução não produz a saída ideal por contra-exemplo. Uma entrada de [6, 2, 1]produz [0, 1, 0, 0, 2, 0, 0, 1, 0]; uma solução melhor é [0, 0, 1, 0, 2, 0, 0, 1, 0].

Este algoritmo trabalha com uma matriz de números inteiros, onde cada número inteiro representa uma categoria diferente. Ele cria matrizes separadas para cada categoria. Por exemplo, se a matriz inicial for [1, 1, 1, 2, 2, 3], ela criará três matrizes, [3], [2, 2], [1, 1, 1].

A partir daí, combina recursivamente as duas matrizes menores (neste exemplo, o [3] e o [2,2]) e espaça a colocação dos elementos da matriz menor na segunda menor matriz, baseada principalmente na proporção do número de ocorrências das categorias maiores e menores. Neste exemplo, terminaríamos com [2,3,2]. Em seguida, usaria essa matriz como a matriz menor que será combinada na próxima matriz maior, até que exista apenas uma matriz.

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

CÓDIGO ANSI C

Esse código funciona imaginando uma linha reta no espaço dimensional n (onde n é o número de categorias) passando pela origem com o vetor direcional (v1, v2, ..., vi, ... vn) em que vi é o número de itens da categoria i. A partir da origem, o objetivo é encontrar o próximo ponto mais próximo da linha. Usando o exemplo [0 0 0 0 0 1 1 1 2 2 2 3], produz o resultado [0 1 2 0 3 1 0 2 0 1 2 0]. Usando o exemplo de Lungj [0 0 0 0 0 0 1 1 2], obtemos [0 1 0 0 2 0 0 1 0], que é exatamente o mesmo que o resultado de Lungj.

O algoritmo é mais eficiente usando apenas aritmética inteira e considerando apenas os deltas entre as distâncias de cada ponto até a linha.

#define MAXCATEGORIES 100

int main () {int i = 0; int j = 0; int tamanho do gato = 0; vetor int [MAXCATEGORIES]; ponto int [MAXCATEGORIES]; int categorias = 0; int totalitems = 0; int melhor = 0; d2 longo = 0L; vp longo = 0L; v2 longo = 0L; delta longo = 0L; beta longo = 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;

}

minha solução:

    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']