Foros del Web » Programando para Internet » PHP »

Problema para pensar

Estas en el tema de Problema para pensar en el foro de PHP en Foros del Web. Hola tengo que hacer esto en php......ojala me puedan ayudar.... Tengo 5 campos.... En el primer campo tengo 19 personas (p1) En el segundo tengo ...
  #1 (permalink)  
Antiguo 30/08/2003, 17:52
Avatar de McManaman  
Fecha de Ingreso: agosto-2003
Ubicación: Ecuador - Guayaquil
Mensajes: 119
Antigüedad: 14 años, 3 meses
Puntos: 0
Mensaje Problema para pensar

Hola tengo que hacer esto en php......ojala me puedan ayudar....

Tengo 5 campos....
En el primer campo tengo 19 personas (p1)
En el segundo tengo 19(p2)
En el tercero tengo 19 (p3)
en el cuarto tengo 19 (p4)
y en el quinto tengo 19(p5)

tengo 19 carros y en cada carro van 5 personas( p1,p2,p3,p4,p5)

Como puedo hacer un programa en php que me ayude a escoger a una persona de cada campo y los seleccione automaticamente de tal manera que una persona no tiene que ver a una misma persona durante 19 dias.....me entienden????
Si el lunes juan estuvo con pedro,maria,luis,carlos al siguiente dia juan no debe verse con esas personas durante los siguientes 18 dias......
__________________
...Hay unos que saben TODO de nada y otros que saben NADA de TODO... think about it
  #2 (permalink)  
Antiguo 30/08/2003, 20:16
O_O
 
Fecha de Ingreso: enero-2002
Ubicación: Santiago - Chile
Mensajes: 34.417
Antigüedad: 15 años, 11 meses
Puntos: 126
Si hablas de "campos" suponemos que esos datos los tienes en alguna Base de datos (no sabemos cual Mysql ? ..) en tal caso todo eso pasa por usar correctamente el lenguaje de consultas SQL de tu motor de BD que uses ( y todo esto en el foro de "base de datos" para comenzar .. )

Avisa si usas BD .. y pon la estructura de datos que uses (la cantidad de datos es indiferente .. lo que cuenta es la estructura).

Un saludo,
__________________
Por motivos personales ya no puedo estar con Uds. Fue grato haber compartido todos estos años. Igualmente los seguiré leyendo.
  #3 (permalink)  
Antiguo 01/09/2003, 17:49
Avatar de McManaman  
Fecha de Ingreso: agosto-2003
Ubicación: Ecuador - Guayaquil
Mensajes: 119
Antigüedad: 14 años, 3 meses
Puntos: 0
je je ta bien sorry ..... uso MySql y todos los campos son varchar... en fin es una rutina en php que tengo que hacer jugando con los select me imagino porque tengo que estar preguntando si ya a sido seleccionado o cosas asi..... gracias
__________________
...Hay unos que saben TODO de nada y otros que saben NADA de TODO... think about it
  #4 (permalink)  
Antiguo 01/09/2003, 22:13
 
Fecha de Ingreso: julio-2003
Mensajes: 165
Antigüedad: 14 años, 5 meses
Puntos: 1
Hola,

Realmente me parece que, en el fondo, este problema que has compartido con nosotros posee un valor muy especial, en tanto que el corazón del problema mismo (al menos como lo he entendido yo) representa un bonito ejercicio de matemática discreta.

Pero bueno, antes de continuar, permíteme replantear el enunciado tal y como lo he interpretado, para efectos de asegurarnos de estar hablando del mismo problema.

Creo que podría escribirse más o menos así: Dados 5 grupos de personas, cada uno de los cuales consta de 19 miembros, encontrar una forma de distribución tal que cada persona sea asignada a uno de 19 carros distintos, durante 19 días, teniendo en cuenta que en cada carro solo puede viajar una persona de cada grupo (es decir, cada carro debe llevar 5 personas cada día), y que cada persona puede cruzarse como máximo solo una vez con cada uno de aquellos con quienes comparte algún carro durante los 19 días.


Partiendo de este problema inicial, y por babélico que parezca en principio :), podrían tomarse varios enfoques distintos en la construcción de una posible solución. En últimas, pienso que la respuesta es más bien sencilla, y la heurística usada para llegar a ella puede ser muy simple, aunque el camino que personalmente he tomado para encontrar una respuesta fue, digamos, interesante... :)

Mi primer instinto fue escribir una solución exhaustiva. Ese tipo de algoritmos que a falta de sofisticación, recurren a la exploración de todos los caminos posibles para encontrar la respuesta a un problema dado. Fue una mala idea. Es una larga e intrigante historia que fui develando a medida que escribía y re-escribía prototipos del algoritmo que tenía en mente, pero básteme con decir que un algoritmo exhaustivo para este tipo de problemas no es tan sencillo como parece en comienzo. Y podría resultar intolerablemente ineficiente.

Así que, inevitablemente, recurrí a la forma divertida: implementar un algoritmo derivado de algún tipo de heurística. También podría dar para una larga y entretenida historia, pero me limitaré a presentar la respuesta a la que llegué finalmente, y que, como dije en un principio, resalta por la simplicidad de su lógica, a diferencia de aquello que tenía en mente inicialmente sobre una posible solución.

El código:

Código:
<?php

/*** Variables personalizables ***/

$n_grupos   = 5;   // Numero de grupos
$n_personas = 19;  // Numero de personas por grupo



/*** Creacion de los datos del programa ***/

$personas = array ();

for ($i = 1; $i <= $n_grupos; $i++) {
    $matriz = "p$i";  // Nombre de cada matriz de personas
    $personas[$matriz] = array ();

    for ($j = 1; $j <= $n_personas; $j++) {
        $persona = "persona$i-$j";  // Nombre de cada persona
        $personas[$matriz][] = $persona;
    }
}



/*** Mostrar el listado de personas ***/

echo <<<FIN
<h3>Existen los siguientes grupos de personas:</h3>
<table>
 <tr>
FIN;

for ($i = 1; $i <= $n_grupos; $i++)
    echo "  <th>p$i</th>\n";

echo " </tr>\n";

for ($i = 0; $i < $n_personas; $i++) {
    echo " <tr>\n";
    
    for ($j = 1; $j <= $n_grupos; $j++)
        echo '  <td>' . $personas["p$j"][$i] . "</td>\n";

    echo " </tr>\n";
}

echo "</table>\n";



/*** Calcular la distribucion de las personas en los carros ***/

$dias = array ();
$personas_cruzadas = array ();
$indices = array (0, 0, 0, 0, 0);

for ($dia = 0; $dia < $n_personas; $dia++) {
    $dias[$dia] = array ();

    $personas_acomodadas = array ();

    for ($carro = 0; $carro < $n_personas; $carro++) {
        $dias[$dia][$carro] = array ();


        for ($grupo = 0; $grupo < $n_grupos; $grupo++) {
            $persona_fue_elegida = false;

            $indice = $indices[$grupo] + $carro;
            if ($indice >= $n_personas)
                $indice %= $n_personas;

            $persona = &$personas['p' . ($grupo + 1)][$indice];

            // Chequear si la persona actual ya se ha cruzado con
            // alguno de los pasajeros ya asignados a este carro

            $se_ha_cruzado = false;

            if (array_key_exists ($persona, $personas_cruzadas)) {
                
                for ($i = 0; $i < $grupo; $i++) {

                    if (in_array ($dias[$dia][$carro][$i],
                                  $personas_cruzadas[$persona])) {

                        $se_ha_cruzado = true;
                        break;
                    }
                }
            }

            
            if (! in_array ($persona, $personas_acomodadas) and
                ! $se_ha_cruzado) {
                
                $persona_fue_elegida = true;
                
                $dias[$dia][$carro][] = $personas_acomodadas[] = $persona;
            }

            if (! $persona_fue_elegida) {
                echo '<p>No es posible acomodar a las personas en los ' .
                    "carros seg&uacute;n los requerimientos.</p>\n";

                exit (1);
            }
        }

        // Llevar el registro de los pasajeros que se han reunido en
        // el carro

        for ($i = 0; $i < $n_grupos; $i++) {
            for ($j = 0; $j < $n_grupos; $j++) {
                if ($i != $j)
                    $personas_cruzadas[$dias[$dia][$carro][$i]][] =
                        $dias[$dia][$carro][$j];
            }
        }

    }

    for ($i = 0, $inc = 1; $i < $n_grupos; $i++, $inc++)
        $indices[$i] = (($indices[$i] + $inc >= $n_personas) ?
                        (($indices[$i] + $inc) % $n_personas) :
                        ($indices[$i] + $inc));
}



/*** Imprimir los resultados ***/

echo "<h3>Resultados de la ubicaci&oacute;n de personas en los carros:</h3>\n";

for ($dia = 0; $dia < $n_personas; $dia++) {
    $dia_num = $dia + 1;

    echo <<<FIN
<table>
 <caption>D&iacute;a $dia_num</caption>
 <tr>
  <th>Carro</th>
  <th colspan="$n_grupos">Pasajeros</th>
 </tr>
FIN;

    for ($carro = 0; $carro < $n_personas; $carro++) {
        echo " <tr>\n  <td>" . ($carro + 1) . "</td>\n";

        for ($pasajero = 0; $pasajero < $n_grupos; $pasajero++)
            echo '  <td>' . $dias[$dia][$carro][$pasajero] . "</td>\n";

        echo " </tr>\n";
    }

    
    echo "</table>\n<br />\n";
}

?>

Este script en la práctica toma un tiempo relativamente alto ejecutándose, en especial por los chequeos que incluye para asegurarse de que las condiciones del enunciado se cumplan. Una vez nos aseguramos de que realmente sí existe al menos una posible solución, podemos retirar los chequeos, y el código podría verse así (solo copio el segmento relevante):


Código:
/*** Calcular la distribucion de las personas en los carros ***/

$dias = array ();
$indices = array (0, 0, 0, 0, 0);

for ($dia = 0; $dia < $n_personas; $dia++) {
    $dias[$dia] = array ();

    for ($carro = 0; $carro < $n_personas; $carro++) {
        $dias[$dia][$carro] = array ();


        for ($grupo = 0; $grupo < $n_grupos; $grupo++) {
            $indice = $indices[$grupo] + $carro;
            if ($indice >= $n_personas)
                $indice %= $n_personas;

            $dias[$dia][$carro][] = $personas['p' . ($grupo + 1)][$indice];
        }
    }

    for ($i = 0, $inc = 1; $i < $n_grupos; $i++, $inc++)
        $indices[$i] = (($indices[$i] + $inc >= $n_personas) ?
                        (($indices[$i] + $inc) % $n_personas) :
                        ($indices[$i] + $inc));
}

El tema de la base de datos, al menos en lo que concierne al algoritmo, es secundario. Ya que mencionas que tienes los datos en una base de datos relacional, podrías, por ejemplo, adaptar el código para cargar los registros en memoria y luego operar sobre ellos. Es decir, el segmento de declaración de los datos del programa podría verse algo así:

Código:
$resultado = mysql_query (
    'SELECT `p1`, `p2`, `p3`, `p4`, `p5` FROM `nombre_tabla`;');

$personas = array ();

if ($resultado) {
    while (($datos = mysql_fetch_row ($resultado))) {
        for ($i = 0; $i < 5; $i++)
            $personas['p' . ($i + 1)][] = $datos[$i];
    }
}

Qué bonito problema... :)

Un cordial saludo
  #5 (permalink)  
Antiguo 01/09/2003, 22:17
Avatar de nuevo  
Fecha de Ingreso: mayo-2003
Ubicación: Spain
Mensajes: 2.009
Antigüedad: 14 años, 7 meses
Puntos: 2

__________________
3w.valenciadjs.com
3w.laislatv.com
  #6 (permalink)  
Antiguo 02/09/2003, 09:44
Avatar de McManaman  
Fecha de Ingreso: agosto-2003
Ubicación: Ecuador - Guayaquil
Mensajes: 119
Antigüedad: 14 años, 3 meses
Puntos: 0
..... muchisimas gracias leonardop....... en verdad me dejaste frio.....te cuento que tenia dos semanas pensando y no llegaba a una solucion......realmente me dejaste helado........una vez mas MUCHAS GRACIAS
__________________
...Hay unos que saben TODO de nada y otros que saben NADA de TODO... think about it
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 15:06.