Algoritmo para distribuir itens "uniformemente"

25

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.

moraes
fonte
Parece que você deseja resolver o problema de ( partição de otimização) , pelo menos aproximadamente. Provavelmente existem muitos algoritmos para esse!
Raphael
Relendo isso, por que contar as ocorrências de todos os valores e depois colocar os valores ciclicamente nem sempre produz a solução ideal?
Raphael

Respostas:

8

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
Jim Mischel
fonte
@DW Por favor, veja minha atualização. Acredito que mostro como meu problema é semelhante ao problema do OP e como meu algoritmo fornece uma solução para o problema do OP.
Jim Mischel
Coisa boa! Obrigado pela excelente atualização. Votado.
DW
Muito interessante, como eu disse anteriormente. A simplicidade da ideia é atraente. Não tive tempo de ler tudo cuidadosamente. Sua solução realmente leva em conta a ciclicidade da pergunta original? Pode haver uma maneira de adaptá-lo para essa finalidade, mas não tenho certeza absoluta.
27515
@babou: Meus cálculos de distância são abrangidos, como você pode ver nos resultados, mas o algoritmo em si não faz nenhuma permissão específica para a natureza cíclica do problema do OP. Também não vejo como adaptar o algoritmo para isso. Ou, a propósito, como levar em conta a natureza cíclica melhoraria os resultados. Embora seja interessante considerar dobrar todas as contagens (isto é, alterar [3,2,1] para [6,4,2]), o que seria efetivamente a mesma coisa. Minha suspeita é que o algoritmo produziria resultados idênticos.
Jim Mischel
6

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).

ttt2xi,jxi,jijt2

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

DW
fonte
Suas sugestões são a maneira padrão de lidar com esses tipos de problemas de agendamento. Eu acho que existe algum software comercial para isso. Como eles lidam com isso?
babou 17/09/14
@babou, ótima pergunta - não faço ideia!
DW
Desenvolvi ainda mais os detalhes do meu algoritmo, mas duvido que muitos aplicativos existentes usariam isso. Na verdade, até me pergunto se os aplicativos de agendamento lidam com um problema desse tipo. Eu tenho solicitado informações sobre o SE.softwarerecs, pois não vejo como fazer a pergunta aqui, exceto como um comentário que acabei de fazer.
babou 17/09/14
A solução ideal pode ser difícil para NP. Mas uma solução bastante viável é O (n log k), onde n é o número total de itens e k é o número de tipos de itens. Veja minha resposta e minha postagem no blog vinculada.
Jim Mischel
2

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.

vn[1..n]ini

nvnvn/nv

v

in/ninmodnin/ni

Isso guiará nosso algoritmo.

n

i|n/niv|

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

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.

babou
fonte
Tenho a mesma impressão de que não importa se começamos com os mais ou menos comuns, deixando os singletons de lado. A estratégia que aparentemente me deu melhores resultados começa a classificar os valores por ocorrência e a colocá-los em ordem a partir dos que ocorrem mais. Isso naturalmente deixa singletons até o fim.
moraes
vn/vV
Você quer dizer que, para uma lista com 10 valores [0, 0, 0, 0, 1, 1, 1, 2, 2, 3]ev 4, colocaríamos os primeiros valores 1( 10/3 = 3.33, mais próximo de v), depois 2( 10/2 = 5, o próximo mais próximo) e depois 0( 10/4 = 2.5)? Ou: você poderia dar um exemplo de "diminuição do desvio médio da distância do valor v"?
Moraes
11
Não, eu faço exatamente o oposto. Tomando seu exemplo, a ordem do posicionamento é primeiro O, pois sua distância média 2,5 se desvia mais de v = 4, depois 2, depois 1 e o singleton 3. - - - O ypu está sugerindo que eu reescreva mais claramente alguns parte da minha explicação para essa estratégia?
babou 10/09/14
Não, está bem. Vou tentar algo ao longo desta idéia e relatar de volta.
Moraes
1

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

lungj
fonte
Acredito que expliquei meu algoritmo nos comentários do código e a base do algoritmo no preâmbulo.
lungj 28/03
Eu teria preferido ver uma descrição independente das idéias por trás do seu algoritmo e pseudocódigo conciso para o algoritmo. Atualmente, o que vejo no texto introdutório é (1) sua abordagem é semelhante à do @ babou e (2) usa uma técnica de anti-aliasing (de alguma forma). Além disso, nem todo mundo aqui lê Python. De qualquer forma, é uma resposta antiga, então eu entendo se você não deseja melhorá-la, mas estou apenas observando nossas expectativas neste site - não apenas para você, mas para outras pessoas que podem percorrer esta página em o futuro e incline-se a responder.
DW
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";
}
vtim
fonte
2
Este não é um site de codificação. Não poste respostas somente de código. Em vez disso, gostaríamos que você explicasse as idéias por trás de sua resposta e forneça um pseudocódigo conciso para seu algoritmo.
DW
Bem-vindo à Ciência da Computação ! No caso de você não estar ciente ou se esquecer por um momento, a leitura do código em um idioma específico é geralmente uma das tarefas mais difíceis que podemos ter, em algum momento, mesmo que o código tenha sido escrito por nós mesmos. Essa é parte da razão pela qual não apreciamos muito o código real neste site, embora possa representar muito mais trabalho do que o pseudocódigo vagamente escrito. Obviamente, eu aprecio todo o código de trabalho real que pode ser executado ou cintilado imediatamente.
Apass.Jack 29/03
A explicação está aí. no código de demonstração comentado; que não em alguma sintaxe arcaica como APL, mas uma sintaxe fácil de entender perto o suficiente para pseudo-código. Ajudaria se minha explicação não estivesse em fonte monoespaçada?
vtim 29/03
Sim. Isso ajuda. Nem todo mundo lê PHP, talvez nem todo mundo possa determinar o que é comentar (talvez seja o argumento do homem da palha) ou simplesmente não deseja ler o bloco de código e interpretá-lo, mas leia a idéia, que você incluiu na parte superior e isso diz tudo. +1 de mim. Seu código é limpo e bem documentado, mas simplesmente não estamos codificando o site, portanto a descrição textual é importante aqui. Obrigado pela sua edição.
Mal
-1

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;

}

DrH
fonte
11
Bem vindo ao site! Em termos de formatação, você precisa recuar cada linha do seu código com quatro espaços, para que o sistema obtenha a marcação correta. Em geral, não estamos procurando grandes blocos de código como respostas às perguntas e, em particular, suas rotinas de entrada de dados não estão adicionando nada aqui. Você tem alguma explicação na parte superior da sua postagem, mas seria melhor expandir isso e reduzir o código.
David Richerby
Este não é um site de codificação. Não poste respostas somente de código. Em vez disso, gostaríamos que você explicasse as idéias por trás de sua resposta e forneça um pseudocódigo conciso para seu algoritmo.
DW
-1

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']
Alexandr Kosolapov
fonte
Por favor, use o pseudocódigo (com alguns comentários necessários) para descrever seu algoritmo.
Xkxzr #
Este não é um site de codificação. Não poste respostas somente de código. Em vez disso, gostaríamos que você explicasse as idéias por trás de sua resposta e forneça um pseudocódigo conciso para seu algoritmo.
DW