Algorithme pour distribuer les articles «uniformément»

25

Je recherche un algorithme pour distribuer les valeurs d'une liste afin que la liste résultante soit aussi "équilibrée" ou "uniformément distribuée" que possible (entre guillemets car je ne suis pas sûr que ce soient les meilleures façons de la décrire ... plus tard, je fournirai un moyen de mesurer si un résultat est meilleur que les autres).

Donc, pour la liste:

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

L'un des meilleurs résultats, après redistribution des valeurs, est:

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

Il peut y avoir d'autres résultats aussi bons que celui-ci, et bien sûr, cela devient plus compliqué avec un ensemble de valeurs moins uniforme.

Voici comment mesurer si un résultat est meilleur que les autres:

  1. Comptez les distances entre chaque élément et l'élément suivant avec la même valeur.

  2. Calculez l'écart type pour cet ensemble de distances. Une dispersion plus faible signifie un meilleur résultat.

Observations:

  • Lorsque vous calculez une distance et que la fin de la liste est atteinte sans trouver un élément avec la même valeur, nous revenons au début de la liste. Donc, tout au plus, le même élément sera trouvé et la distance pour cet élément sera la longueur de la liste. Cela signifie que la liste est cyclique ;
  • Une liste typique comprend ~ 50 articles avec ~ 15 valeurs différentes en quantités variées.

Alors:

  • Pour le résultat [1, 2, 3, 1, 2, 3], les distances sont [3, 3, 3, 3, 3, 3]et l'écart type est 0;
  • Pour le résultat [1, 1, 2, 2, 3, 3], les distances sont [1, 5, 1, 5, 1, 5]et l'écart type est 2;
  • Ce qui rend le premier résultat meilleur que le second (un écart inférieur est meilleur).

Compte tenu de ces définitions, je demande un indice des algorithmes ou stratégies à rechercher.

moraes
la source
On dirait que vous voulez résoudre le (variante d'optimisation du) problème de partition , au moins approximativement. Il y a probablement de nombreux algorithmes pour celui-là!
Raphael
En relisant cela, pourquoi le fait de compter les occurrences de toutes les valeurs puis de placer cycliquement les valeurs ne donne-t-il pas toujours la solution optimale?
Raphael

Réponses:

8

J'ai rencontré cette question tout en recherchant un problème similaire: des ajouts optimaux de liquides pour réduire la stratification. Il semble que ma solution soit également applicable à votre situation.

Si vous voulez mélanger les liquides A, B et C dans la proportion 30,20,10 (c'est-à-dire 30 unités de A, 20 unités de B et 10 unités de C), vous vous retrouvez avec une stratification si vous ajoutez tous le A, puis tout le B, puis tout le C. Il vaut mieux mélanger des unités plus petites. Par exemple, effectuez des ajouts d'unité dans la séquence [A, B, A, C, B, A]. Cela empêchera complètement la stratification.

La façon dont je l'ai trouvé est de le traiter comme une sorte de fusion, en utilisant une file d'attente prioritaire. Si je crée une structure pour décrire les ajouts:

MergeItem
    Item, Count, Frequency, Priority

La fréquence est exprimée comme "un tous les N". Ainsi, A, qui est ajouté trois fois sur six, a une fréquence de 2 (6/3).

Et initialisez un tas qui contient initialement:

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

Maintenant, je supprime le premier élément du tas et je le génère. Ensuite, réduisez son nombre de 1 et augmentez la priorité par fréquence et ajoutez-le au tas. Le tas résultant est:

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

Ensuite, supprimez B du tas, éditez-le et mettez-le à jour, puis rajoutez-le au tas:

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

Si je continue de cette façon, j'obtiens le mélange souhaité. J'utilise un comparateur personnalisé pour m'assurer que lorsque des éléments de priorité égaux sont insérés dans le tas, celui avec la valeur de fréquence la plus élevée (c'est-à-dire la moins fréquente) est commandé en premier.

J'ai écrit une description plus complète du problème et de sa solution sur mon blog, et présenté un code C # fonctionnel qui l'illustre. Voir Répartition uniforme des éléments dans une liste .

Mettre à jour après les commentaires

Je pense que mon problème est similaire au problème de l'OP, et donc que ma solution est potentiellement utile. Je m'excuse de ne pas avoir cadré ma réponse davantage dans les termes de la question du PO.

La première objection, que ma solution utilise A, B et C plutôt que 0, 1 et 2, est facilement corrigée. C'est simplement une question de nomenclature. Je trouve plus facile et moins déroutant de penser et de dire "deux A" plutôt que "deux 1". Mais aux fins de cette discussion, j'ai modifié mes sorties ci-dessous pour utiliser la nomenclature du PO.

Bien sûr, mon problème concerne le concept de distance. Si vous voulez "répartir uniformément les choses", la distance est implicite. Mais, encore une fois, c'était mon échec de ne pas montrer de manière adéquate comment mon problème est similaire au problème du PO.

J'ai effectué quelques tests avec les deux exemples fournis par l'OP. C'est:

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

Dans ma nomenclature, ceux-ci sont exprimés respectivement en [2,2,2] et [4,3,2,1]. Soit, dans le dernier exemple, "4 éléments de type 0, 3 éléments de type 1, 2 éléments de type 2 et 1 élément de type 3."

J'ai exécuté mon programme de test (comme décrit ci-dessous) et j'ai publié mes résultats. En l'absence de données de l'OP, je ne peux pas dire si mes résultats sont similaires, pires ou meilleurs que les siens. Je ne peux pas non plus comparer mes résultats à ceux des autres parce que personne d'autre n'en a publié.

Je peux dire, cependant, que l'algorithme fournit une bonne solution à mon problème d'élimination de la stratification lors du mélange de liquides. Et il semble qu'il offre une solution raisonnable au problème du PO.

Pour les résultats ci-dessous, j'ai utilisé l'algorithme que j'ai détaillé dans mon article de blog, avec la priorité initiale définie sur Frequency/2et le comparateur de tas modifié pour favoriser l'élément le plus fréquent. Le code modifié est affiché ici, avec les lignes modifiées commentées.

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

En exécutant mon programme de test avec le premier exemple de l'OP, j'obtiens:

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

Donc mon algorithme fonctionne pour le problème trivial de tous les comptes étant égaux.

Pour le deuxième problème signalé par l'OP, j'ai obtenu:

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

Je ne vois pas de moyen évident d'améliorer cela. Il pourrait être réorganisé pour faire les distances pour l'élément 0 [2,3,2,3] ou un autre arrangement de 2 et 3, mais cela changera les écarts pour les éléments 1 et / ou 2. Je ne sais vraiment pas quoi "optimum" est dans cette situation. Est-il préférable d'avoir un écart plus important sur les éléments les plus fréquents ou les moins fréquents?

En l'absence d'autres problèmes de l'OP, j'ai utilisé ses descriptions pour en inventer quelques-unes. Il a déclaré dans son message:

Une liste typique comprend ~ 50 articles avec ~ 15 valeurs différentes en quantités variées.

Mes deux tests ont donc été:

[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

Et mes résultats:

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

Et pour le deuxième exemple:

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
la source
@DW Veuillez voir ma mise à jour. Je crois que je montre comment mon problème est similaire au problème de l'OP, et comment mon algorithme fournit une solution au problème de l'OP.
Jim Mischel
Bon produit! Merci pour l'excellente mise à jour. A voté.
DW
Assez intéressant, comme je l'ai dit précédemment. La simplicité de l'idée est séduisante. Je n'ai pas eu le temps de tout lire attentivement. Votre solution prend-elle réellement en compte la cyclicité de la question d'origine? Il peut y avoir un moyen de l'adapter à cet effet, mais je ne suis pas complètement sûr de savoir s'il se réveille.
babou
@babou: Mes calculs de distance s'enroulent, comme vous pouvez le voir dans les résultats, mais l'algorithme lui-même ne tient pas compte spécifiquement de la nature cyclique du problème du PO. Je ne vois pas non plus de moyen d'adapter l'algorithme à cette fin. Ou, d'ailleurs, comment la prise en compte de la nature cyclique améliorerait les résultats. Bien qu'il soit intéressant d'envisager de doubler tous les nombres (c'est-à-dire de changer [3,2,1] en [6,4,2]), ce qui serait en fait la même chose. Je soupçonne que l'algorithme produirait des résultats identiques.
Jim Mischel
6

Cela "sent" comme s'il pouvait être NP-dur. Alors, que faites-vous quand vous avez un problème NP-difficile? Lancez une heuristique ou un algorithme d'approximation, ou utilisez un solveur SAT.

Dans votre cas, si vous n'avez pas besoin de la solution optimale absolue, un point de départ raisonnable pourrait être d'essayer un recuit simulé . Il existe un moyen naturel de prendre n'importe quelle solution candidate et de la déplacer vers une solution candidate proche: choisissez au hasard deux éléments de la liste et échangez-les. Le recuit simulé tentera de manière itérative d'améliorer la solution. Vous pouvez trouver de nombreuses ressources sur le recuit simulé, si vous ne le connaissez pas. Vous pouvez également expérimenter avec d'autres ensembles de «mouvements locaux» qui apportent de petits changements à une solution candidate, dans l'espoir de l'améliorer progressivement (c.-à-d. Réduire l'écart type des distances).

ttt2xi,jxi,jijt2

Mais je vous suggère de commencer par un recuit simulé. C'est la première chose que j'essaierais, car je pense que cela pourrait bien fonctionner.

DW
la source
Vos suggestions sont-elles le moyen standard de résoudre ces types de problèmes de planification? Je suppose qu'il existe des logiciels commerciaux pour cela. Comment le gèrent-ils?
babou
@babou, grande question - je n'en ai aucune idée!
DW
J'ai développé les détails de mon algorithme, mais je doute que beaucoup d'applications existantes l'utilisent. En fait, je me demande même si la planification des applications traite un problème de ce type. J'ai demandé des informations sur SE.softwarerecs, car je ne vois pas comment poser la question ici, sinon comme un commentaire comme je viens de le faire.
babou
La solution optimale pourrait être NP-difficile. Mais une solution tout à fait réalisable est O (n log k), où n est le nombre total d'éléments et k est le nombre de types d'éléments. Voir ma réponse et mon article de blog lié.
Jim Mischel
2

Esquisse d'un algorithme heuristique

Je n'ai pas de solution exacte à ce problème. Mais comme le commentaire de Raphaël suggère qu'il ressemble au problème de partition, pour lequel des algorithmes heuristiques ont été développés, je vais essayer une approche heuristique. Ce n'est qu'un croquis d'un algorithme heuristique.

vn[1..n]ini

nvnvn/nv

v

in/ninmodnin/ni

Cela guidera notre algorithme.

n

i|n/niv|

Il peut s'agir d'une valeur avec très peu ou très peu d'occurrences au début. Je pense que cela ne fait pas vraiment de différence, car les contraintes créées par l'occupation des créneaux sont proportionnelles au nombre de valeurs bien (?) Placées.

La première valeur considérée peut être placée sans aucune contrainte. Ensuite, les autres valeurs doivent être placées de manière à minimiser leur contribution à l'écart-type, mais uniquement dans les emplacements laissés libres par les valeurs précédemment placées.

Le placement des occurrences d'une valeur dans les emplacements restants peut être fait avec un algorithme de programmation dynamique, de manière à fusionner les calculs qui placent le même nombre de valeurs entre deux positions, en ne gardant que celles qui ont une contribution minimale à l'écart-type (c'est-à-dire valeur minimale pour la somme des carrés de leurs écarts).

v

j|n/njv|

Ensuite, vous placez les valeurs singleton dans les emplacements restants.

Je crois que cela devrait généralement donner une solution raisonnable, mais je n'ai encore aucune idée de la façon de le prouver ou d'estimer l'écart avec une solution optimale.

babou
la source
J'ai la même impression que cela n'a pas d'importance si nous commençons par les plus ou les moins courants, en laissant de côté les singletons. La stratégie qui m'a apparemment donné les meilleurs résultats commence à trier les valeurs par occurrence et à les placer dans l'ordre en commençant par celles qui se produisent le plus. Cela laisse naturellement les singletons à la fin.
moraes
vn/vV
Voulez-vous dire que, pour une liste avec 10 valeurs [0, 0, 0, 0, 1, 1, 1, 2, 2, 3]et v 4, nous placerions d'abord les valeurs 1( 10/3 = 3.33, les plus proches de v), puis 2( 10/2 = 5, les plus proches suivantes), puis 0( 10/4 = 2.5)? Ou: pourriez-vous donner un exemple de "diminution de l'écart moyen de la distance par rapport à la valeur v"?
moraes
1
Non, je fais juste le contraire. En prenant votre exemple, l'ordre de positionnement est d'abord O puisque sa distance moyenne 2,5 s'écarte le plus de v = 4, puis 2, puis 1, et le singleton 3. - - - Ypu suggère-t-il que je devrais réécrire plus clairement certains une partie de mon explication de cette stratégie?
babou
Non ça va. Je vais essayer quelque chose le long de cette idée et faire rapport.
moraes
1

Il semble que je sois très en retard à la fête, mais je poste au cas où quelqu'un se heurterait à nouveau à cela. Ma solution est similaire à @ babou's plus. Plus tôt dans la journée, j'ai eu un problème de planification dans un système embarqué qui m'a conduit à ce fil. J'ai une implémentation spécifique à mon problème en C, mais j'ai pensé publier une solution plus générique en Python ici (la version C est compliquée par le fait que je me suis limité à une petite pile de taille fixe et pas de mémoire allocations, donc j'exécute tout l'algorithme sur place). La technique d'anticrénelage utilisée ci-dessous est quelque chose que vous pourriez utiliser pour dessiner une ligne sur un écran avec une couleur de 2 bits. L'algorithme atteint ici un score inférieur (c'est-à-dire meilleur) lorsqu'il est mesuré en utilisant la somme de l'écart-type pour les entrées utilisées par Jim Mischel que cette solution particulière.

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

résultats pour

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)

Si des entrées de la forme spécifiée par @moraes sont fournies, on peut la convertir en une forme utilisable par cette fonction en étapes O (n) en utilisant des bits de mémoire Big Omega (n * log (n)) où n est le nombre d'éléments ( dans une liste de 255 éléments, vous n'aurez pas besoin de plus de 255 octets supplémentaires) en conservant un tableau parallèle avec le nombre de répétitions. Alternativement, on peut effectuer une paire de tri sur place avec O (1) mémoire supplémentaire.

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: je sais que cette solution ne produit pas la sortie optimale par contre-exemple. Une entrée de [6, 2, 1]produit [0, 1, 0, 0, 2, 0, 0, 1, 0]; une meilleure solution est [0, 0, 1, 0, 2, 0, 0, 1, 0].

lungj
la source
Je crois que j'ai expliqué mon algorithme dans les commentaires de code et la base de l'algorithme dans le préambule.
lungj
J'aurais préféré voir une description autonome des idées derrière votre algorithme et un pseudocode concis pour l'algorithme. Actuellement, ce que je vois dans le texte d'introduction est (1) votre approche est similaire à celle de @ babou et (2) elle utilise une technique d'anti-aliasing (en quelque sorte). De plus, tout le monde ici ne lit pas Python. En tout cas, c'est une vieille réponse, donc je comprends si vous ne voulez pas l'améliorer, mais je note juste nos attentes sur ce site - pas seulement pour vous, mais pour d'autres qui pourraient parcourir cette page en l'avenir et être enclin à répondre.
DW
0

Cet algorithme fonctionne avec un tableau d'entiers, où chaque entier représente une catégorie différente. Il crée des tableaux séparés pour chaque catégorie. Par exemple, si le tableau de départ est [1, 1, 1, 2, 2, 3], il créera trois tableaux, [3], [2, 2], [1, 1, 1].

De là, il combine récursivement les deux plus petits tableaux (dans cet exemple, les [3] et [2,2]) et espace le placement des éléments du plus petit tableau dans le deuxième plus petit tableau basé principalement sur le rapport du nombre des occurrences des catégories plus grandes vs plus petites. Dans cet exemple, nous finirions avec [2,3,2]. Ensuite, il utiliserait ce tableau comme le plus petit tableau qui sera combiné dans le prochain tableau plus grand, jusqu'à ce qu'il ne reste qu'un seul tableau.

<?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
la source
2
Ce n'est pas un site de codage. Veuillez ne pas publier de réponses uniquement en code. Au lieu de cela, nous aimerions que vous expliquiez les idées derrière votre réponse et fournissiez un pseudocode concis pour votre algorithme.
DW
Bienvenue en informatique ! Juste au cas où vous ne seriez pas au courant ou que vous avez oublié pendant un moment, la lecture de code dans une langue particulière est généralement l'une des tâches les plus difficiles que nous puissions avoir, parfois même si le code a été écrit par nous-mêmes. C'est en partie la raison pour laquelle nous n'apprécions pas beaucoup le vrai code sur ce site, bien qu'il puisse représenter beaucoup plus de travail qu'un pseudocode vaguement écrit. Bien sûr, j'apprécie tout le code de travail réel qui peut être exécuté ou scintillé immédiatement.
Apass.Jack
L'explication est là. dans le code de démonstration commenté; qui pas dans une syntaxe archaïque comme APL, mais une syntaxe facile à comprendre assez proche du pseudo code. Serait-il utile que mon explication ne soit pas en police monospace?
Vtim
Oui. Ça aide. Tout le monde ne lit pas PHP, peut-être que tout le monde ne peut pas déterminer ce qu'est un commentaire (c'est peut-être l'argument de l'homme de paille) ou simplement ne veut pas lire le bloc de code et l'interpréter, mais lisez l'idée, que vous avez incluse en haut et ça raconte tout. +1 de moi. Votre code est propre et bien documenté, mais nous ne sommes tout simplement pas un site de codage, donc la description textuelle est importante ici. Merci pour ton montage.
Evil
-1

CODE ANSI C

Ce code fonctionne en imaginant une ligne droite dans un espace dimensionnel n (où n est le nombre de catégories) passant par l'origine avec un vecteur directionnel (v1, v2, ..., vi, ... vn) où vi est le nombre de articles de la catégorie i. En partant de l'origine, le but est de trouver le prochain point le plus proche de la ligne. En utilisant l'exemple [0 0 0 0 0 1 1 1 2 2 2 3], il produit le résultat [0 1 2 0 3 1 0 2 0 1 2 0]. En utilisant l'exemple de Lungj [0 0 0 0 0 0 1 1 2] nous obtenons [0 1 0 0 2 0 0 1 0], qui est exactement le même que le résultat de Lungj.

L'algorithme est rendu plus efficace en utilisant uniquement l'arithmétique entière et en ne considérant que les deltas entre les distances de chaque point à la ligne.

#define MAXCATEGORIES 100

int main () {int i = 0; int j = 0; int chatsize = 0; vecteur int [MAXCATEGORIES]; int point [MAXCATEGORIES]; catégories int = 0; int totalitems = 0; int meilleur = 0; long d2 = 0L; vp long = 0L; long v2 = 0L; delta long = 0L; bêta longue = 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
la source
1
Bienvenue sur le site! Au niveau du formatage, vous devez mettre en retrait chaque ligne de votre code avec quatre espaces afin que le système obtienne le bon balisage. En général, nous ne recherchons pas de gros blocs de code comme réponses aux questions et, en particulier, vos routines de saisie de données n'ajoutent rien ici. Vous avez des explications en haut de votre message, mais il serait préférable de développer cela et de réduire le code.
David Richerby
Ce n'est pas un site de codage. Veuillez ne pas publier de réponses uniquement en code. Au lieu de cela, nous aimerions que vous expliquiez les idées derrière votre réponse et fournissiez un pseudocode concis pour votre algorithme.
DW
-1

ma 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']
Alexandr Kosolapov
la source
Veuillez utiliser un pseudocode (avec quelques commentaires nécessaires) pour décrire votre algorithme.
xskxzr
Ce n'est pas un site de codage. Veuillez ne pas publier de réponses uniquement en code. Au lieu de cela, nous aimerions que vous expliquiez les idées derrière votre réponse et fournissiez un pseudocode concis pour votre algorithme.
DW