Necesito un algoritmo para dividir una serie de números

Después de algunas noches ocupadas mi cabeza no está funcionando tan bien, pero esto debe solucionarse ayer, por lo que le pido a la comunidad más renovada de SO.Necesito un algoritmo para dividir una serie de números

Tengo una serie de números. Por ejemplo:

1, 5, 7, 13, 3, 3, 4, 1, 8, 6, 6, 6

I necesidad de dividir esta serie en tres partes por lo que la suma de los números en todas las partes es lo más cercano posible. El orden de los números debe mantenerse, por lo que la primera parte debe consistir en los primeros números X, el segundo - de los próximos números Y, y el tercero - de lo que quede.

¿Cuál sería el algoritmo para hacer esto?

(Nota: el problema real es organizar párrafos de texto de diferentes alturas en tres columnas. Los párrafos deben mantener el orden (por supuesto) y no pueden dividirse a la mitad. Las columnas deben ser lo más iguales posible.)

Fuente

2011-10-13 Vilx-

pregunta duplicados? http://stackoverflow.com/questions/3009146/splitting-values-into-groups-evenly – kan

Cerrar, pero permite la reorganización de valores. Creo que mi caso debería ser más simple, pero el algoritmo mencionado aquí no es útil aquí. –

Tres partes: ¿es este el requisito o solo un ejemplo? –

En primer lugar, tendremos que definir el objetivo mejor:

Supongamos que las sumas parciales son A1, A2, A3, estamos tratando de minimizar | A-A1 | + | A-A2 | + | A-A3 |. A es el promedio: A = (A1 + A2 + A3)/3.

Por lo tanto, estamos tratando de minimizar | A2 + A3-2A1 | + | A1 + A3-2A2 | + | A1 + A2-2A3 |.

Deje que S denote la suma (que es constante): S = A1 + A2 + A3, por lo que A3 = S-A1-A2.

que estamos tratando de reducir al mínimo:

| A2 + S-A1-A2-2A1 | + | A1 + S-A1-A2-2A2 | + | + A1 + A2-2S 2A1 2A2 + | = | S-3A1 | + | S-3A2 | + | 3A1 + SA2-2S |

Denotando esta función como f, podemos hacer dos bucles O (n^2) y realizar un seguimiento del mínimo:

Algo así como:

for (x=1; x<items; x++) 
{ 
    A1= sum(Item[0]..Item[x-1]) 
    for (y=x; y<items; y++) 
    { 
     A2= sum(Item[x]..Item[y-1]) 
     calc f, if new minimum found -keep x,y 
    } 
}

Fuente

2011-10-13 09:12:58

Bueno, esto es simple. Y veo cómo esto podría adaptarse a otra "función de costos", similar al algoritmo de Knuth. No es eficiente, pero se pueden hacer mejoras. Por otro lado, raramente (si es que alguna vez) conseguiré más de 20 grupos de todos modos, así que tal vez esto sea incluso el mejor en términos de mantenibilidad. –

arriba algo es en realidad [fuerza bruta algo] O (n^3), n^2 para dos bucles yn para suma en bucle interno. – vikas368

@ vikas368: en realidad no. Solo necesita agregar un solo elemento en cada iteración. Lo escribí de esta manera solo por claridad. –

Creo que esto se puede resolver con a dynamic programming algorithm for line breaking inventado por Donald Knuth para su uso en TeX.

Fuente

2011-10-13 08:46:14

Interesante, pero ese algoritmo se basa en un tamaño de línea máximo conocido. Mis columnas no tienen límite, solo necesitan estar lo más cerca posible para dar un resultado estéticamente agradable. –

Creo que el algoritmo es para dividir una secuencia de números en cualquier cantidad de segmentos, cada uno de los cuales tiene como máximo un valor k dado y un tamaño similar entre ellos como sea posible. Lo que queremos aquí es dividir la secuencia en un número fijo de segmentos (3) que sean de tamaño similar entre sí, lo que es ligeramente diferente. Pero aún podría ser útil intentar configurar k = suma/3 o menos. –

encontrar suma y suma acumulada de serie.

obtener una suma =/3

a continuación, busque más cercana a, 2 * a en la suma acumulativa que divide la lista en tres partes iguales.

Fuente

2011-10-13 08:57:42 vikas368

Siguiendo la respuesta de Aasmund Eldhuset, previamente respondí esta pregunta en SO.

Word wrap to X lines instead of maximum width (Least raggedness)

Este algo no se basa en el tamaño máximo de la línea, pero sólo da un corte óptimo.

he modificado para que funcione con su problema:

L=[1,5,7,13,3,3,4,1,8,6,6,6] 

def minragged(words, n=3): 


P=2 
cumwordwidth = [0] 
# cumwordwidth[-1] is the last element 
for word in words: 
    cumwordwidth.append(cumwordwidth[-1] + word) 
totalwidth = cumwordwidth[-1] + len(words) - 1 # len(words) - 1 spaces 
linewidth = float(totalwidth - (n - 1))/float(n) # n - 1 line breaks 

print "number of words:", len(words) 
def cost(i, j): 
    """ 
    cost of a line words[i], ..., words[j - 1] (words[i:j]) 
    """ 
    actuallinewidth = max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i]) 
    return (linewidth - float(actuallinewidth)) ** P 

""" 
printing the reasoning and reversing the return list 
""" 
F={} # Total cost function 

for stage in range(n): 
    print "------------------------------------" 
    print "stage :",stage 
    print "------------------------------------" 
    print "word i to j in line",stage,"\t\tTotalCost (f(j))" 
    print "------------------------------------" 


    if stage==0: 
     F[stage]=[] 
     i=0 
     for j in range(i,len(words)+1): 
      print "i=",i,"j=",j,"\t\t\t",cost(i,j) 
      F[stage].append([cost(i,j),0]) 
    elif stage==(n-1): 
     F[stage]=[[float('inf'),0] for i in range(len(words)+1)] 
     for i in range(len(words)+1): 
       j=len(words) 
       if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]: #calculating min cost (cf f formula) 
        F[stage][j][0]=F[stage-1][i][0]+cost(i,j) 
        F[stage][j][1]=i 
        print "i=",i,"j=",j,"\t\t\t",F[stage][j][0]    
    else: 
     F[stage]=[[float('inf'),0] for i in range(len(words)+1)] 
     for i in range(len(words)+1): 
      for j in range(i,len(words)+1): 
       if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]: 
        F[stage][j][0]=F[stage-1][i][0]+cost(i,j) 
        F[stage][j][1]=i 
        print "i=",i,"j=",j,"\t\t\t",F[stage][j][0] 

print 'reversing list' 
print "------------------------------------" 
listWords=[] 
a=len(words) 
for k in xrange(n-1,0,-1):#reverse loop from n-1 to 1 
    listWords.append(words[F[k][a][1]:a]) 
    a=F[k][a][1] 
listWords.append(words[0:a]) 
listWords.reverse() 

for line in listWords: 
    print line, '\t\t',sum(line) 

return listWords

el resultado que obtengo es:

[1, 5, 7, 13]  26 
[3, 3, 4, 1, 8]   19 
[6, 6, 6]  18 
[[1, 5, 7, 13], [3, 3, 4, 1, 8], [6, 6, 6]]

Espero que ayuda

Fuente

2011-10-13 09:09:04

Uff, python. No es uno de los idiomas con los que estoy muy familiarizado. Tomará un tiempo para roer. Estoy tentado de comenzar con la solución de Lior Kogan, agregar una función de costos diferente y un par de optimizaciones para reducir el recuento de ciclos. Como mi serie generalmente será corta (20 ítems son grandes), un algoritmo cuadrático tampoco es tan malo. Pero mientras tanto, ¡tenga un voto positivo! :) –

@ Vilx- Traté de escribir un algo que sigue paso a paso el programa dinámico para obtener el mínimo desgarre, por lo que no debería ser muy difícil de entender. Pero puedes encontrar muchas versiones (especialmente una en C#) de este código en el enlace que publiqué en la parte superior de mi respuesta. –

Gracias. C# es lo mío. :) –

permite decir p es su gama de alturas párrafo;

int len= p.sum()/3; //it is avarage value 
int currlen=0; 
int templen=0; 
int indexes[2]; 
int j = 0; 
for (i=0;i<p.lenght;i++) 
{ 
    currlen = currlen + p[i]; 
    if (currlen>len) 
    { 
     if ((currlen-len)<(abs((currlen-p[i])-len)) 
     { //check which one is closer to avarege val 
      indexes[j++] = i; 
      len=(p.sum()-currlen)/2   //optional: count new avearege height from remaining lengths 
      currlen = 0; 
     } 
     else 
     { 
      indexes[j++] = i-1; 
      len=(p.sum()-currlen)/2 
      currlen = p[i]; 
     } 
    } 
    if (j>2) 
     break; 
}

Obtendrá el índice inicial de la 2da y 3ra secuencia. Tenga en cuenta su tipo de pseudo código :)

Fuente

2011-10-13 09:10:25 Zaphood

Todavía merece ser formateado. OK, entiendo la idea. –

Necesito un algoritmo para dividir una serie de números

Respuesta

Cuestiones relacionadas