Programa para equipos

[mauricho]

No es muy claro el titulo, no se como titularlo.

La idea es armar un programa, que tenga cierta cantidad de nombres de personas, con un puntaje del 1 al 10, lo cual de esa lista pueda seleccionar a 10 personas, luego al correr el programa, que automaticamente lo divida en 2 grupos, y que la suma de cada grupo, entre si, de casi similar.

Osea, selecciono 10 nombres, y la suma de los grupos da A=43; B=45, necesito que me muestre los nombres, como fueron dividos.

Mas que nada necesitaria el algoritmo matematico, la cuenta que tendria que hacer para que sume y pruebe hasta que den parecido las dos sumas.

Gracias.

El fin del programa, es para armar equipos de futbol entre amigos, siempre estamos 10 minutos viendo quienes somos y repartiendonos para que salga parejo el partido. Entonces la idea es tener un puntaje para cada uno, y correr el programa con los presentes y probar si resulta XD.

[Pantaláimon]

Interesante.

No lo he comprobado pero intuyo que para obtener el resultado óptimo deberías ordenar las personas según su puntuación de mayor a menor.

Luego deberías ir cogiendo repetidamente la persona con mayor puntuación y ponerla en el grupo que la suma sea de menor puntuación hasta que hayas repartido todas la personas en los dos grupos.

Edit: no es el algoritmo optimo. Por ejemplo hay las siguientes puntuaciones
51,49,35,32,31
Según mi algoritmo quedaría:
Grupo A: 51, 32, 31
Grupo B: 49, 35

Cuando
Grupo A: 51, 49
Grupo B: 35, 32, 31
es una repartición mejor.

Supongo que habrá que usar algún algoritmo de grafos.
Un saludo!

[mauricho]

Tendria que ser un loop que sume 5 y 5 y el resultado de las dos sumas los reste entre si, cuando da en un rango de -5 a 5, ya estaria "equilibrado".

Calculo que una pc no tardaria en probar todas las combinaciones hasta que de el resultado. Tengo las ideas pero muy incompletas.

Necesito armar la lista primero, con 20 elementos. (a, b, c, d, e, f, g, h, i, j, k, l..etc) cada elemento asignarle un valor, del 1 al 10.

Cuando selecciono 10 que empieze a sumar a+b+c+d+e y f+g+h+i+j, el resultado lo resta entre si, si da -5 -4 -3 -2 -1 0 1 2 3 4 5 que muestre que sumas hizo, si no, que entre de nuevo al loop y sume, no se b+c+d+e+f y a+g+h+i+j y asi.

¿lo ven posible?

[mauricho]

Si me dan una mano, paso a paso, creo que puedo llegar a resolverlo.
Lo primero que necesito es armar la lista de los elemtos con el valor oculto, poder seleccionar 10, y apretar un boton que me vaya a otra pagina, sacar de la url los elemtos con los valores ocultos.

Opcion 1 []
Opcion 2 []
Opcion 3 []
Opcion n []
Opcion .. []

"calcuclar >>"

opcion 2 = 4
opcion 3 = 8
opcion n = n

Si me pueden facilitar eso, de ahi, yo guardo todo un variable diferentes y veo como hago el loop.

[Alexis88]

Se me ocurre algo como esto:

Código Javascript:

var todos = [5, 2, 3, 8, 4, 7, 5, 9, 6, 2],
    grupo1 = [], grupo2 = [], tot1 = 0, tot2 = 0;
 
grupo1.push(Math.max.apply(null, todos)); //Obtengo el valor mayor y lo inserto en 'grupo1'
tot1 += Math.max.apply(null, todos); //Acumulo el valor en 'tot1'
todos.splice(todos.indexOf(Math.max.apply(null, todos)), 1); //Y lo quito de 'todos'
 
grupo2.push(Math.max.apply(null, todos)); //Obtengo el nuevo valor mayor y lo inserto en 'grupo2'
tot2 += Math.max.apply(null, todos); //Acumulo el valor en 'tot2'
todos.splice(todos.indexOf(Math.max.apply(null, todos)), 1); //Y lo quito de 'todos'
 
for (var i = 0, l = todos.length; i < l; i++){
    r = tot1 - tot2;
    if (r <= 5 && r >= -5){
        if (tot1 > tot2){
            grupo2.push(todos[i]);
            tot2 += todos[i];
        }
        else{
            grupo1.push(todos[i]);
            tot1 += todos[i];
        }
    }
    else{
        if (tot1 > tot2){
            grupo2.push(todos[i]);
            tot2 += todos[i];
        }
        else{
            grupo1.push(todos[i]);
            tot1 += todos[i];
        }
    }
}
 
console.log(grupo1, grupo2); //[9, 2, 3, 7, 6] [8, 5, 4, 5, 2] | tot1 - tot2 = 3
 

Trabajando con los rangos que estableciste en uno de tus comentarios, la adición de elementos a un array u otro dependerá ya sea de si la diferencia se encuentra dentro del rango. Quizá pueda hacerse esto de una manera más eficiente, esta es solo una primitiva y básica idea.

Edito: Repensando el algoritmo, creo que es mejor empezar por tomar a los dos mayores valores del array inicial, colocarlos en los arrays y a partir de ahí empezar la selección. Como cuando los dos mejores son los que forman a los equipos en un partido de fútbol entre amigos (al menos así jugábamos ).

Saludos

[zerokilled]

buenas...
la naturaleza del tema me resulta un ejercicio interesante, asi que no pude evitar intentarlo. solo que lo hice en lapiz y papel con diferentes secuencias tratando de buscar un patron. mas o menos este es el modelo que tengo:

• reparte todos los numeros en dos grupos. puede ser aleatorio, secuencial, de uno en uno, u otro metodo. no importa el metodo, pues el objetivo principal no es darle un orden a los grupos.
• intercambia (swap) los valores de la misma posicion en ambos arrays, moviendo el numero mayor hacia el array que la suma sea menor.
• repites el proceso de intercambio con el resto de las posiciones hasta que la diferencia de ambos arrays se aproxime al limite de lo que se considera "estable". en tu ejemplo, -5 a 5.

no digo que sea el mejor metodo, pero quizas sea bastante razonable. la diferencia con el metodo de alexis es que su algoritmo desde un principio va asignando los valores en condicion de la suma computada. tampoco parte de la premisa de balancear la carga asignando los numeros mayores en distintos grupos. si bien entiendo el argumento valido de que los valores mayores (mejores del equipo) son la base del grupo, en teoria los grupos se balancean cuando la suma son lo suficiente similar.

luego de tenerlo funcionando y para complicar mas el ejercicio, lo interesante seria generalizar el algoritmo para que dado X numeros, los reparta en partes iguales para X numero de grupos.

[marlanga]

Backtracking puro, sobre un algoritmo óptimo de selección general (cualquier número de equipos, cualquier diferencia máxima de tamaño de equipo).

Se puede mejorar mucho, haciendo ramificación y poda. Pero como las operaciones que realiza son sencillas, para 20 elementos no tiene demasiado coste de tiempo (2 segundos, por lo menos en una cpu i5).
A partir de ahí empieza a dispararse el tiempo, por lo que para meter mas elementos se estaría obligado a podar.

http://jsfiddle.net/marlanga/1aqzp30q/

Código Javascript:

Array.prototype.sum = function() {
    return this.length ? this.reduce(
        function(a, b) {
            return a + b;
        }
    ) : 0;
}
 
function Equipo(){
    this.miembros = [];
}
 
Equipo.prototype.pop = function() {
    return this.miembros.pop();
}
 
Equipo.prototype.push = function(miembro) {
    this.miembros.push(miembro);
}
 
Equipo.prototype.sumar = function() {
    return this.miembros.sum();
}
 
Equipo.prototype.length = function() {
    return this.miembros.length;
}
 
Equipo.prototype.clonar = function() {
    var clon = new Equipo();
    for (var i = 0, n = this.miembros.length; i < n; i++) {
        clon.push(this.miembros[i]);
    }
    return clon;
}
 
function RyP(disponibles, numero_equipos, cantidad_miembros_diferencia) {
    this.disponibles = disponibles;
    this.equipos=[];
    this.nEquipos = numero_equipos;
    this.cantidad_miembros_diferencia = cantidad_miembros_diferencia;
 
    this.mejor_solucion = {
        diferencia : Infinity,
        equipos : null
    };
 
    this.crearEquipos();
}
 
RyP.prototype.crearEquipos = function() {
    for(var i = 0; i < this.nEquipos; i++) {
        this.equipos.push(new Equipo());
    }
}
 
RyP.prototype.exec = function() {
    if (this.disponibles.length === 0) {
        this.comparaSolucion();
    } else {
        var miembro = this.disponibles.pop();
        for(var i = 0; i < this.nEquipos; i++) {
            this.equipos[i].push(miembro);
            this.exec();
            this.equipos[i].pop();
        }
        this.disponibles.push(miembro);
    }
}
 
RyP.prototype.comparaSolucion = function() {
    if (this.maximaDiferenciaCantidadMiembros() > this.cantidad_miembros_diferencia) return;
    var diff = this.maximaDiferenciaPesoEquipo();
    if (diff >= this.mejor_solucion.diferencia) return;
 
    this.mejor_solucion.diferencia = diff;
    var clon_equipos = [];
    for(var i = 0; i < this.nEquipos; i++) {
        clon_equipos.push(this.equipos[i].clonar());
    }
    this.mejor_solucion.equipos = clon_equipos;
}
 
RyP.prototype.maximaDiferenciaCantidadMiembros = function() {
    return this.maximaDiferencia();
}
 
RyP.prototype.maximaDiferenciaPesoEquipo = function() {
    return this.maximaDiferencia(true);
}
 
RyP.prototype.maximaDiferencia = function(condicion) {
    var menor = condicion ? this.equipos[0].sumar() : this.equipos[0].length();
    var mayor = menor;
 
    for(var i = 1; i < this.nEquipos; i++) {
        var length = condicion ? this.equipos[i].sumar() :  this.equipos[i].length();
        menor = Math.min(length, menor);
        mayor = Math.max(length, mayor);
    }
 
    return Math.abs(mayor - menor);
}
 
 
 
var miembros = [51,49,35,32,31];
var numero_equipos = 2;
var diferencia_maxima_cantidad_miembros_por_equipo = 1;
var resolvedor = new RyP(miembros,numero_equipos, diferencia_maxima_cantidad_miembros_por_equipo);
resolvedor.exec();
console.log(resolvedor.mejor_solucion);