Algoritmo para distribuir elementos "uniformemente"

25

Estoy buscando un algoritmo para distribuir valores de una lista para que la lista resultante esté lo más "equilibrada" o "distribuida de manera uniforme" posible (entre comillas porque no estoy seguro de que estas sean las mejores formas de describirla ... más adelante proporcionaré una forma de medir si un resultado es mejor que otro).

Entonces, para la lista:

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

Uno de los mejores resultados, después de redistribuir los valores, es:

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

Puede haber otros resultados tan buenos como este y, por supuesto, esto se vuelve más complicado con un conjunto de valores menos uniforme.

Así es como medir si un resultado es mejor que otro:

  1. Cuente las distancias entre cada elemento y el siguiente elemento con el mismo valor.

  2. Calcule la desviación estándar para ese conjunto de distancias. Una dispersión más baja significa un mejor resultado.

Observaciones:

  • Cuando se calcula una distancia y se alcanza el final de la lista sin encontrar un elemento con el mismo valor, volvemos al principio de la lista. Entonces, a lo sumo, se encontrará el mismo artículo y la distancia para ese artículo será la longitud de la lista. Esto significa que la lista es cíclica ;
  • Una lista típica tiene ~ 50 artículos con ~ 15 valores diferentes en cantidades variadas.

Asi que:

  • Para el resultado [1, 2, 3, 1, 2, 3], las distancias son [3, 3, 3, 3, 3, 3]y la desviación estándar es 0;
  • Para el resultado [1, 1, 2, 2, 3, 3], las distancias son [1, 5, 1, 5, 1, 5]y la desviación estándar es 2;
  • Lo que hace que el primer resultado sea mejor que el segundo (una desviación menor es mejor).

Dadas estas definiciones, pido una pista de qué algoritmos o estrategias debo buscar.

moraes
fuente
Parece que quiere resolver el problema ( Partición de optimización del) Partición , al menos de forma aproximada. ¡Probablemente haya muchos algoritmos para ese!
Raphael
Al volver a leer esto, ¿por qué contar las ocurrencias de todos los valores y luego colocar valores cíclicamente no siempre produce la solución óptima?
Raphael

Respuestas:

8

Me encontré con esta pregunta mientras investigaba un problema similar: adiciones óptimas de líquidos para reducir la estratificación. Parece que mi solución también sería aplicable a su situación.

Si desea mezclar líquidos A, B y C en la proporción de 30,20,10 (es decir, 30 unidades de A, 20 unidades de B y 10 unidades de C), terminará con la estratificación si agrega todos la A, luego toda la B y luego toda la C. Es mejor mezclar unidades más pequeñas. Por ejemplo, haga adiciones de una sola unidad en la secuencia [A, B, A, C, B, A]. Eso evitará la estratificación por completo.

La forma en que lo hice es tratarlo como una especie de fusión, utilizando una cola de prioridad. Si creo una estructura para describir las adiciones:

MergeItem
    Item, Count, Frequency, Priority

La frecuencia se expresa como "uno cada N". Entonces, A, que se agrega tres de seis veces, tiene una frecuencia de 2 (6/3).

E inicialice un montón que inicialmente contiene:

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

Ahora, elimino el primer elemento del montón y lo envío. Luego reduzca su recuento en 1 y aumente la Prioridad por Frecuencia y agréguelo nuevamente al montón. El montón resultante es:

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

A continuación, elimine B del montón, la salida y actualícela, luego agregue nuevamente al montón:

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

Si continúo de esa manera, obtengo la mezcla deseada. Utilizo un comparador personalizado para garantizar que cuando se insertan elementos de prioridad iguales en el montón, se ordena primero el que tiene el valor de frecuencia más alto (es decir, el menos frecuente).

Escribí una descripción más completa del problema y su solución en mi blog, y presenté un código C # que lo ilustra. Consulte Distribución uniforme de elementos en una lista .

Actualización después de comentarios

Creo que mi problema es similar al del OP y, por lo tanto, mi solución es potencialmente útil. Pido disculpas por no enmarcar mi respuesta más en los términos de la pregunta del OP.

La primera objeción, que mi solución está usando A, B y C en lugar de 0, 1 y 2, se soluciona fácilmente. Es simplemente una cuestión de nomenclatura. Me resulta más fácil y menos confuso pensar y decir "dos A" en lugar de "dos 1". Pero para los propósitos de esta discusión, he modificado mis resultados a continuación para usar la nomenclatura del OP.

Por supuesto, mi problema trata con el concepto de distancia. Si desea "distribuir las cosas de manera uniforme", la distancia está implícita. Pero, nuevamente, fue mi fracaso por no mostrar adecuadamente cómo mi problema es similar al problema del OP.

Ejecuté algunas pruebas con los dos ejemplos que proporcionó el OP. Es decir:

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

En mi nomenclatura, esos se expresan como [2,2,2] y [4,3,2,1], respectivamente. Es decir, en el último ejemplo, "4 elementos del tipo 0, 3 elementos del tipo 1, 2 elementos del tipo 2 y 1 elemento del tipo 3".

Ejecuté mi programa de prueba (como se describe a continuación) y publiqué mis resultados. En ausencia del aporte del OP, no puedo decir si mis resultados son similares, peores o mejores que los suyos. Tampoco puedo comparar mis resultados con los resultados de nadie más porque nadie más ha publicado ninguno.

Sin embargo, puedo decir que el algoritmo proporciona una buena solución a mi problema de eliminar la estratificación al mezclar líquidos. Y parece que proporciona una solución razonable al problema del OP.

Para los resultados que se muestran a continuación, utilicé el algoritmo que detallé en mi entrada de blog, con la prioridad inicial establecida en Frequency/2, y el comparador de montón modificado para favorecer el elemento más frecuente. El código modificado se muestra aquí, con las líneas 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;
    }
}

Al ejecutar mi programa de prueba con el primer ejemplo del OP, obtengo:

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

Entonces mi algoritmo funciona para el problema trivial de que todos los recuentos sean iguales.

Para el segundo problema que publicó el OP, obtuve:

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

No veo una forma obvia de mejorar eso. Podría reorganizarse para hacer las distancias para el ítem 0 [2,3,2,3] o algún otro arreglo de 2 y 3, pero eso cambiará las desviaciones para los ítems 1 y / o 2. Realmente no sé qué "óptimo" está en esta situación. ¿Es mejor tener una desviación mayor en los artículos más frecuentes o menos frecuentes?

Al carecer de otros problemas del OP, utilicé sus descripciones para inventar algunas propias. Él dijo en su publicación:

Una lista típica tiene ~ 50 artículos con ~ 15 valores diferentes en cantidades variadas.

Entonces mis dos pruebas fueron:

[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

Y mis 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

Y para el segundo ejemplo:

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
fuente
@DW Por favor vea mi actualización. Creo que muestro cómo mi problema es similar al problema del OP, y cómo mi algoritmo proporciona una solución al problema del OP.
Jim Mischel
¡Buen material! Gracias por la excelente actualización. Votado
DW
Muy interesante, como dije anteriormente. La simplicidad de la idea es atractiva. No tuve tiempo de leerlo todo con cuidado. ¿Su solución realmente tiene en cuenta la ciclicidad de la pregunta original? Puede haber una forma de adaptarlo para ese propósito, pero no estoy completamente seguro de si funciona.
babou
@babou: Mis cálculos de distancia se completan, como puede ver en los resultados, pero el algoritmo en sí no tiene en cuenta la naturaleza cíclica del problema del OP. Tampoco veo ninguna forma de adaptar el algoritmo para hacerlo. O, para el caso, cómo tomar en cuenta la naturaleza cíclica mejoraría los resultados. Aunque es interesante considerar duplicar todos los recuentos (es decir, cambiar [3,2,1] a [6,4,2]), lo que sería efectivamente lo mismo. Mi sospecha es que el algoritmo produciría resultados idénticos.
Jim Mischel
6

Esto "huele" como si pudiera ser NP-duro. Entonces, ¿qué haces cuando tienes un problema NP-difícil? Lánzale una heurística o un algoritmo de aproximación, o usa un solucionador SAT.

En su caso, si no necesita la solución óptima absoluta, un punto de partida razonable podría ser intentar el recocido simulado . Hay una forma natural de tomar cualquier solución candidata y moverla a una solución candidata cercana: seleccione aleatoriamente dos elementos de la lista y cámbielos. El recocido simulado intentará iterativamente mejorar la solución. Puede encontrar muchos recursos en recocido simulado, si no está familiarizado con él. También puede experimentar con otros conjuntos de "movimientos locales" que realizan pequeños cambios en una solución candidata, con la esperanza de mejorarla gradualmente (es decir, reducir la desviación estándar de las distancias).

ttt2xi,jxi,jijt2

Pero te sugiero que comiences con recocido simulado. Eso es lo primero que intentaría, porque creo que podría funcionar.

DW
fuente
¿Son sus sugerencias la forma estándar de abordar este tipo de problemas de programación? Supongo que hay algún software comercial para esto. ¿Cómo lo manejan?
babou
@babou, gran pregunta - ¡No tengo idea!
DW
Desarrollé aún más los detalles de mi algoritmo, pero dudo que muchas aplicaciones existentes lo usen. En realidad, incluso me pregunto si las aplicaciones de programación abordan un problema de este tipo. He estado pidiendo información sobre SE.softwarerecs, ya que no veo cómo hacer la pregunta aquí, aparte de un comentario como acabo de hacer.
babou
La solución óptima puede ser NP-hard. Pero una solución bastante viable es O (n log k), donde n es el número total de elementos yk es el número de tipos de elementos. Vea mi respuesta y mi publicación de blog vinculada.
Jim Mischel
2

Bosquejo de un algoritmo heurístico

No tengo una solución exacta para este problema. Pero como el comentario de Raphael sugiere que se parece al problema de la partición, para el cual se han desarrollado algoritmos heurísticos, intentaré un enfoque heurístico. Esto es solo un boceto de un algoritmo heurístico.

vn[1..n]ini

nvnvn/nv

v

in/ninmodnin/ni

Eso guiará nuestro algoritmo.

n

i|n/niv|

Puede ser un valor con muchas o muy pocas ocurrencias al principio. Creo que en realidad no hace la diferencia, ya que las restricciones creadas por ocupar ranuras están en proporción al número de valores bien (?) Colocados.

El primer valor considerado se puede colocar sin ninguna restricción. Luego, los otros valores deben colocarse para minimizar su contribución a la desviación estándar, pero solo en los espacios que quedan libres por los valores que se hayan colocado antes.

La colocación de las ocurrencias de un valor en los espacios restantes se puede hacer con un algoritmo de programación dinámico, para fusionar los cálculos que colocan el mismo número de valores entre dos posiciones, manteniendo solo aquellos que tienen una contribución mínima a la desviación estándar (es decir, valor mínimo para la suma del cuadrado de sus desviaciones).

v

j|n/njv|

Luego coloca los valores singleton en las ranuras restantes.

Creo que esto generalmente debería dar una solución razonable, pero aún no tengo idea de cómo probarlo o estimar la brecha con una solución óptima.

babou
fuente
Tengo la misma impresión de que no importa si comenzamos con los más o menos comunes, dejando de lado los singletons. La estrategia que aparentemente me dio mejores resultados comienza ordenando los valores por ocurrencia y ordenándolos a partir de los que ocurren más. Esto, naturalmente, deja singletons hasta el final.
moraes
vn/vV
¿Quiere decir que, para una lista con 10 valores [0, 0, 0, 0, 1, 1, 1, 2, 2, 3]yv 4, colocaríamos primero los valores 1( 10/3 = 3.33, más cercano a v), luego 2( 10/2 = 5, siguiente más cercano), luego 0( 10/4 = 2.5)? O: ¿podría dar un ejemplo de "disminución de la desviación media de la distancia del valor v"?
moraes
1
No, yo hago todo lo contrario. Tomando su ejemplo, el orden de posicionamiento es primero O ya que su distancia media 2,5 se desvía más de v = 4, luego 2, luego 1, y el singleton 3. - - - Están sugiriendo que debería reescribir más claramente algunos parte de mi explicación para esta estrategia?
babou
No, esta bien. Probaré algo junto con esta idea e informaré.
moraes
1

Parece que llego muy tarde a la fiesta, pero publicando en caso de que alguien se encuentre con esto nuevamente. Mi solución es similar a @ babou's plus. Hoy temprano, tuve un problema de programación en un sistema embebido que me llevó a este hilo. Tengo una implementación específica para mi problema en C, pero pensé que publicaría una solución más genérica en Python aquí (la versión C es complicada por el hecho de que me he restringido a una pila pequeña de tamaño fijo y sin memoria asignaciones, por lo que realizo todo el algoritmo en el lugar). La técnica de suavizado utilizada a continuación es algo que puede usar para dibujar una línea en una pantalla con color de 2 bits. El algoritmo aquí logra una puntuación más baja (es decir, mejor) cuando se mide usando la suma de la desviación estándar para las entradas utilizadas por Jim Mischel que esa solución en particular.

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)

Si se proporcionan entradas de la forma especificada por @moraes, se puede convertir a una forma utilizable por esta función en pasos O (n) utilizando Big Omega (n * log (n)) bits de memoria donde n es el número de elementos ( en una lista con 255 elementos, no necesitará más de 255 bytes adicionales) manteniendo una matriz paralela con los recuentos de repetición. Alternativamente, uno puede realizar un par de clases en el lugar con O (1) memoria adicional.

PD

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)

Editar: Sé que esta solución no produce la salida óptima por contraejemplo. Una entrada de [6, 2, 1]produce [0, 1, 0, 0, 2, 0, 0, 1, 0]; Una mejor solución es [0, 0, 1, 0, 2, 0, 0, 1, 0].

lungj
fuente
Creo que expliqué mi algoritmo en los comentarios del código y la base del algoritmo en el preámbulo.
lungj
Hubiera preferido ver una descripción independiente de las ideas detrás de su algoritmo y un seudocódigo conciso para el algoritmo. Actualmente, lo que veo en el texto introductorio es (1) su enfoque es similar al de @ babou y (2) utiliza una técnica de suavizado (de alguna manera). Además, no todos aquí leen Python. En cualquier caso, es una respuesta antigua, por lo que entiendo si no desea mejorarla, pero solo estoy notando nuestras expectativas en este sitio, no solo para usted, sino para otros que podrían encontrar esta página en el futuro e inclinado a responder.
DW
0

Este algoritmo funciona con una matriz de enteros, donde cada entero representa una categoría diferente. Crea matrices separadas para cada categoría. Por ejemplo, si la matriz inicial es [1, 1, 1, 2, 2, 3], creará tres matrices, [3], [2, 2], [1, 1, 1].

A partir de ahí, combina recursivamente las dos matrices más pequeñas (en este ejemplo, [3] y [2,2]) y espacia la ubicación de los elementos de la matriz más pequeña en la segunda matriz más pequeña, basándose principalmente en la relación del número de ocurrencias de las categorías más grandes frente a las más pequeñas. En este ejemplo, terminaríamos con [2,3,2]. Luego usaría esta matriz como la matriz más pequeña que se combinará en la siguiente matriz más grande, hasta que solo quede una 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
fuente
2
Este no es un sitio de codificación. No publique respuestas de solo código. En cambio, nos gustaría que explique las ideas detrás de su respuesta y que proporcione un seudocódigo conciso para su algoritmo.
DW
¡Bienvenido a Computer Science ! En caso de que no lo supiera o lo olvidara por un momento, leer el código en un idioma en particular suele ser una de las tareas más difíciles que podemos tener, incluso si el código fue escrito por nosotros mismos. Esa es parte de la razón por la cual no apreciamos mucho el código real en este sitio, aunque podría representar mucho más trabajo que el pseudocódigo escrito libremente. Por supuesto, aprecio todo el código de trabajo real que se puede ejecutar o parpadear de inmediato.
Apass.Jack
La explicación está ahí. en el código de demostración comentado; que no está en una sintaxis arcaica como APL, pero es una sintaxis fácil de entender lo suficientemente cerca del pseudocódigo. ¿Ayudaría si mi explicación no estuviera en fuente monoespacio?
vtim
Sí. Sí ayuda. No todos leen PHP, tal vez no todos puedan determinar qué es un comentario (tal vez sea un argumento de hombre de paja) o simplemente no quieren leer el bloque de código e interpretarlo, pero lean la idea, que ha incluido en la parte superior y lo dice todo +1 de mi parte Su código está limpio y bien documentado, pero simplemente no estamos codificando el sitio, por lo que la descripción textual es importante aquí. Gracias por tu edición.
Mal
-1

CÓDIGO ANSI C

Este código funciona imaginando una línea recta en n espacio dimensional (donde n es el número de categorías) que pasa por el origen con el vector direccional (v1, v2, ..., vi, ... vn) donde vi es el número de artículos en la categoría i. Comenzando desde el origen, el objetivo es encontrar el siguiente punto más cercano a la línea. Usando el ejemplo [0 0 0 0 0 1 1 1 2 2 2 3] produce el resultado [0 1 2 0 3 1 0 2 0 1 2 0]. Usando el ejemplo de Lungj [0 0 0 0 0 0 1 1 2] obtenemos [0 1 0 0 2 0 0 1 0], que es exactamente el mismo que el resultado de Lungj.

El algoritmo se hace más eficiente usando solo aritmética de enteros y considerando solo los deltas entre las distancias desde cada punto a la línea.

#define MAXCATEGORIES 100

int main () {int i = 0; int j = 0; int catsize = 0; int vector [MAXCATEGORIES]; punto int [MAXCATEGORIES]; int categorías = 0; int totalitems = 0; int mejor = 0; largo d2 = 0L; largo vp = 0L; largo v2 = 0L; delta largo = 0L; beta largo = 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
fuente
1
Bienvenido al sitio! En cuanto al formato, debe sangrar cada línea de su código con cuatro espacios para que el sistema obtenga el marcado correcto. En general, no estamos buscando grandes bloques de código como respuestas a preguntas y, en particular, sus rutinas de entrada de datos no agregan nada aquí. Tienes alguna explicación en la parte superior de tu publicación, pero sería mejor expandir eso y reducir el código.
David Richerby
Este no es un sitio de codificación. No publique respuestas de solo código. En cambio, nos gustaría que explique las ideas detrás de su respuesta y que proporcione un seudocódigo conciso para su algoritmo.
DW
-1

mi solución:

    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
fuente
Utilice el seudocódigo (con algunos comentarios necesarios) para describir su algoritmo.
xskxzr
Este no es un sitio de codificación. No publique respuestas de solo código. En cambio, nos gustaría que explique las ideas detrás de su respuesta y que proporcione un seudocódigo conciso para su algoritmo.
DW