Algoritmo para dividir una lista de números en 2 listas de sum igual

Hay una lista de números.

La lista se dividirá en 2 listas del mismo tamaño, con una diferencia mínima en la sum. Las sums tienen que ser impresas.

#Example: >>>que = [2,3,10,5,8,9,7,3,5,2] >>>make_teams(que) 27 27 

¿Hay algún error en el siguiente algoritmo de código para algún caso?

¿Cómo optimizo y / o pythonize esto?

 def make_teams(que): que.sort() if len(que)%2: que.insert(0,0) t1,t2 = [],[] while que: val = (que.pop(), que.pop()) if sum(t1)>sum(t2): t2.append(val[0]) t1.append(val[1]) else: t1.append(val[0]) t2.append(val[1]) print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n" 

La pregunta es de http://www.codechef.com/problems/TEAMSEL/

    Nueva solucion

    Esta es una búsqueda de amplitud en primer lugar con la selección heurística. El árbol está limitado a una profundidad de jugadores / 2. El límite de la sum del jugador es total de puntuaciones / 2. Con un grupo de 100 jugadores, tardó aproximadamente 10 segundos en resolverse.

     def team(t): iterations = range(2, len(t)/2+1) totalscore = sum(t) halftotalscore = totalscore/2.0 oldmoves = {} for p in t: people_left = t[:] people_left.remove(p) oldmoves[p] = people_left if iterations == []: solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys())) return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]]) for n in iterations: newmoves = {} for total, roster in oldmoves.iteritems(): for p in roster: people_left = roster[:] people_left.remove(p) newtotal = total+p if newtotal > halftotalscore: continue newmoves[newtotal] = people_left oldmoves = newmoves solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys())) return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]]) print team([90,200,100]) print team([2,3,10,5,8,9,7,3,5,2]) print team([1,1,1,1,1,1,1,1,1,9]) print team([87,100,28,67,68,41,67,1]) print team([1, 1, 50, 50, 50, 1000]) #output #(200, 190, [90, 100]) #(27, 27, [3, 9, 7, 3, 5]) #(5, 13, [1, 1, 1, 1, 9]) #(229, 230, [28, 67, 68, 67]) #(150, 1002, [1, 1, 1000]) 

    También tenga en cuenta que intenté resolver esto utilizando la descripción de GS, pero es imposible obtener suficiente información simplemente almacenando los totales acumulados. Y si almacena tanto el número de elementos como los totales, entonces sería el mismo que para esta solución, excepto que guardó datos innecesarios. Porque solo necesitas mantener las n-1 y n iteraciones hasta numplayers / 2.

    Tenía uno antiguo y exhaustivo basado en coeficientes binomiales (ver en la historia). Resolvió los problemas de ejemplo de longitud 10 muy bien, pero luego vi que la competencia tenía gente de hasta 100 personas.

    La progtwigción dinámica es la solución que estás buscando.

    Ejemplo con [4, 3, 10, 3, 2, 5]:

     Eje X: sum alcanzable del grupo.  max = sum (todos los números) / 2 (redondeado hacia arriba)
     Eje Y: Contar elementos en grupo.  max = conteo de números / 2 (redondeado hacia arriba)
    
           1 2 3 4 5 6 7 8 9 10 11 12 13 14
      1 |  |  |  |  4 |  |  |  |  |  |  |  |  |  |  |  // 4
      2 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
      3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    
           1 2 3 4 5 6 7 8 9 10 11 12 13 14
      1 |  |  |  3 |  4 |  |  |  |  |  |  |  |  |  |  |  // 3
      2 |  |  |  |  |  |  |  3 |  |  |  |  |  |  |  |
      3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    
           1 2 3 4 5 6 7 8 9 10 11 12 13 14
      1 |  |  |  3 |  4 |  |  |  |  |  | 10 |  |  |  |  |  // 10
      2 |  |  |  |  |  |  |  3 |  |  |  |  |  | 10 | 10 |
      3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
    
           1 2 3 4 5 6 7 8 9 10 11 12 13 14
      1 |  |  |  3 |  4 |  |  |  |  |  | 10 |  |  |  |  |  // 3
      2 |  |  |  |  |  |  3 |  3 |  |  |  |  |  | 10 | 10 |
      3 |  |  |  |  |  |  |  |  |  |  3 |  |  |  |  |
    
           1 2 3 4 5 6 7 8 9 10 11 12 13 14
      1 |  |  2 |  3 |  4 |  |  |  |  |  | 10 |  |  |  |  |  // 2
      2 |  |  |  |  |  2 |  3 |  3 |  |  |  |  |  2 | 10 | 10 |
      3 |  |  |  |  |  |  |  |  2 |  2 |  3 |  |  |  |  |
    
           1 2 3 4 5 6 7 8 9 10 11 12 13 14
      1 |  |  2 |  3 |  4 |  5 |  |  |  |  | 10 |  |  |  |  |  // 5
      2 |  |  |  |  |  2 |  3 |  3 |  5 |  5 |  |  |  2 | 10 | 10 |
      3 |  |  |  |  |  |  |  |  2 |  2 |  3 |  5 |  5 |  |  |
                                            ^
    

    12 es nuestro numero de la suerte! Backtracing para obtener el grupo:

     12 - 5 = 7 {5}
      7 - 3 = 4 {5, 3}
      4 - 4 = 0 {5, 3, 4}
    

    El otro conjunto se puede calcular: {4,3,10,3,2,5} – {5,3,4} = {10,3,2}

    Todos los campos con un número son posibles soluciones para una bolsa. Elija el que está más lejos en la esquina inferior derecha.

    BTW: Se llama el problema de la mochila .

    Si todos los pesos (w1, …, wn y W) son enteros no negativos, el problema de la mochila se puede resolver en tiempo pseudo-polinomial utilizando la progtwigción dinámica.

    Bueno, puede encontrar una solución a un porcentaje de precisión en el tiempo polinomial, pero para encontrar realmente la solución óptima (diferencia mínima absoluta), el problema es NP-completo. Esto significa que no hay una solución de tiempo polinomial para el problema. Como resultado, incluso con una lista relativamente pequeña de números, es demasiado computacional para resolver. Si realmente necesita una solución, eche un vistazo a algunos de los algoritmos de aproximación para esto.

    http://en.wikipedia.org/wiki/Subset_sum_problem

    P. Dado un conjunto múltiple de S de enteros , ¿hay una manera de dividir S en dos subconjuntos S1 y S2 de tal manera que la sum de los números en S1 sea igual a la sum de los números en S2?

    A. Establecer problema de partición .

    La mejor de las suertes se acerca. 🙂

    Tenga en cuenta que también es una heurística y que eliminé el tipo de función.

      def g(data): sums = [0, 0] for pair in zip(data[::2], data[1::2]): item1, item2 = sorted(pair) sums = sorted([sums[0] + item2, sums[1] + item1]) print sums data = sorted([2,3,10,5,8,9,7,3,5,2]) g(data) 

    En realidad es PARTICIÓN, un caso especial de KNAPSACK.

    Es NP Completo, con algoritmos pseudo-polinomiales dp. El pseudo en pseudo-polinomio se refiere al hecho de que el tiempo de ejecución depende del rango de los pesos.

    En general, primero deberá decidir si existe una solución exacta antes de poder admitir una solución heurística.

    Un caso de prueba donde tu método no funciona es

     que = [1, 1, 50, 50, 50, 1000] 

    El problema es que estás analizando cosas en pares, y en este ejemplo, quieres que todos los 50 estén en el mismo grupo. Esto debería resolverse, sin embargo, si elimina el aspecto de análisis de pares y solo hace una entrada a la vez.

    Aquí está el código que hace esto.

     def make_teams(que): que.sort() que.reverse() if len(que)%2: que.insert(0,0) t1,t2 = [],[] while que: if abs(len(t1)-len(t2))>=len(que): [t1, t2][len(t1)>len(t2)].append(que.pop(0)) else: [t1, t2][sum(t1)>sum(t2)].append(que.pop(0)) print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n" if __name__=="__main__": que = [2,3,10,5,8,9,7,3,5,2] make_teams(que) que = [1, 1, 50, 50, 50, 1000] make_teams(que) 

    Esto da 27, 27 y 150, 1002, que son las respuestas que tienen sentido para mí.

    Edit: En resumen, encuentro que esto no funciona, aunque al final, no estoy muy seguro de por qué. Voy a publicar mi código de prueba aquí, ya que podría ser útil. La prueba solo genera una secuencia aleatoria que tiene sums iguales, las pone juntas y las compara (con resultados tristes).

    Edición # 2: Basado en el ejemplo señalado por Desconocido, [87,100,28,67,68,41,67,1] , está claro por qué mi método no funciona. Específicamente, para resolver este ejemplo, los dos números más grandes deben agregarse a la misma secuencia para obtener una solución válida.

     def make_sequence(): """return the sums and the sequence that's devided to make this sum""" while 1: seq_len = randint(5, 200) seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)] seqs = [[], []] for i in range(seq_len): for j in (0, 1): seqs[j].append(randint(1, seq_max)) diff = sum(seqs[0])-sum(seqs[1]) if abs(diff)>=seq_max: continue if diff<0: seqs[0][-1] += -diff else: seqs[1][-1] += diff return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1] if __name__=="__main__": for i in range(10): s0, s1, seq0, seq1 = make_sequence() t0, t1 = make_teams(seq0+seq1) print s0, s1, t0, t1 if s0 != t0 or s1 != t1: print "FAILURE", s0, s1, t0, t1 

    Obviamente están buscando una solución de mochila de progtwigción dinámica. Así que después de mi primer esfuerzo (una heurística original bastante buena, pensé), y mi segundo esfuerzo (una solución combinatoria exacta realmente astuta que funcionó para conjuntos de datos cortos, e incluso para conjuntos de hasta 100 elementos, siempre que el número de valores únicos fuera bajo), finalmente sucumbí a la presión de los compañeros y escribí la que querían (no demasiado difícil: el manejo de las entradas duplicadas fue la parte más difícil; el algoritmo subyacente en el que se basa solo funciona si todas las entradas son únicas; estoy seguro de que largo es lo suficientemente grande como para contener 50 bits!).

    Por lo tanto, para todos los datos de prueba y los casos incómodos que reuní al probar mis dos primeros esfuerzos, da la misma respuesta. Al menos para los que consulté con el solucionador combinatorio, que son correctos. ¡Pero todavía estoy fallando la presentación con alguna respuesta incorrecta!

    No le estoy pidiendo a nadie que arregle mi código aquí, pero sería de gran ayuda si alguien pudiera encontrar un caso en el que el siguiente código genere la respuesta incorrecta.

    Gracias,

    Graham

    PS Este código siempre se ejecuta dentro del límite de tiempo, pero está lejos de estar optimizado. Lo mantengo simple hasta que pasa la prueba, luego tengo algunas ideas para acelerarlo, tal vez por un factor de 10 o más.

     #include 
    
     #define TRUE (0 == 0)
     # define FALSO (0! = 0)
    
     static int debug = TRUE;
    
     // int simple (const void * a, const void * b) {
     // return * (int *) a - * (int *) b;
     //}
    
     int main (int argc, char ** argv) {
       int p [101];
       char * s, línea [128];
       máscara larga larga, c0 [45001], c1 [45001];
       int skill, jugadores, objective, i, j, pruebas, total = 0;
    
       debug = (argc == 2 && argv [1] [0] == '-' && argv [1] [1] == 'd' && argv [1] [2] == '\ 0');
    
       s = fgets (línea, 127, estándar);
       pruebas = atoi (s);
       while (pruebas -> 0) {
    
         para (i = 0; i <45001; i ++) {c0 [i] = 0LL;}
    
         s = fgets (línea, 127, estándar);  /* linea en blanco */
         s = fgets (línea, 127, estándar);  / * no de jugadores * /
         jugadores = atoi (s);
         para (i = 0; i  0; i--) {
           if (debug || (c0 [i] & mask)) {
             fprintf (stdout, "% d% d \ n", i, total-i);
             if (debug) {
               if (c0 [i] & mask) printf ("******** [");  más
               printf ("[");
               para (j = 0; j <= jugadores; j ++) si (c0 [i] y (1LL << (largo largo) j)) printf ("% d", j + 1);
               printf ("] \ n");
             } de lo contrario romper
           }
         }
         }
         if (tests) printf ("\ n");
       }
       devuelve 0;
     }
    
     class Team(object): def __init__(self): self.members = [] self.total = 0 def add(self, m): self.members.append(m) self.total += m def __cmp__(self, other): return cmp(self.total, other.total) def make_teams(ns): ns.sort(reverse = True) t1, t2 = Team(), Team() for n in ns: t = t1 if t1 < t2 else t2 t.add(n) return t1, t2 if __name__ == "__main__": import sys t1, t2 = make_teams([int(s) for s in sys.argv[1:]]) print t1.members, sum(t1.members) print t2.members, sum(t2.members) >python two_piles.py 1 50 50 100 [50, 50] 100 [100, 1] 101 

    Para el rendimiento, se guardan los cálculos al reemplazar append () y sum () con totales acumulados.

    Podría apretar un poco su bucle usando lo siguiente:

     def make_teams(que): que.sort() t1, t2 = [] while que: t1.append(que.pop()) if sum(t1) > sum(t2): t2, t1 = t1, t2 print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)) 

    Dado que las listas deben ser iguales, el problema no es NP en absoluto.

    Divido la lista ordenada con el patrón t1 <-que (primero, último), t2 <-que (segundo, último-1) ...

     def make_teams2(que): que.sort() if len(que)%2: que.insert(0,0) t1 = [] t2 = [] while que: if len(que) > 2: t1.append(que.pop(0)) t1.append(que.pop()) t2.append(que.pop(0)) t2.append(que.pop()) else: t1.append(que.pop(0)) t2.append(que.pop()) print sum(t1), sum(t2), "\n" 

    Edición : Supongo que esto también es un método incorrecto. ¡Resultados erróneos!

    Después de pensar un poco, no por un gran problema, creo que el mejor tipo de heurística será algo como:

     import random def f(data, nb_iter=20): diff = None sums = (None, None) for _ in xrange(nb_iter): random.shuffle(data) mid = len(data)/2 sum1 = sum(data[:mid]) sum2 = sum(data[mid:]) if diff is None or abs(sum1 - sum2) < diff: sums = (sum1, sum2) print sums 

    Puedes ajustar nb_iter si el problema es mayor.

    Resuelve todos los problemas mencionados anteriormente, principalmente todos los tiempos.

    En un comentario anterior, formulé la hipótesis de que el problema tal como estaba establecido era manejable porque habían elegido cuidadosamente los datos de prueba para que fueran compatibles con varios algoritmos dentro del tiempo asignado. Esto resultó no ser el caso, sino las limitaciones del problema, los números que no superan los 450 y un conjunto final que no supera los 50 números es la clave. Estos son compatibles para resolver el problema usando la solución de progtwigción dinámica que puse en una publicación posterior. Ninguno de los otros algoritmos (heurística, o enumeración exhaustiva por un generador de patrones combinatorios) puede funcionar porque habrá casos de prueba lo suficientemente grandes o lo suficientemente fuertes como para romper esos algoritmos. Es bastante molesto ser honesto porque esas otras soluciones son más desafiantes y ciertamente más divertidas. Tenga en cuenta que sin mucho trabajo adicional, la solución de progtwigción dinámica simplemente dice si una solución es posible con N / 2 para una sum determinada, pero no le informa el contenido de ninguna de las particiones.