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ú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ón de personas en los carros:</h3>\n";
for ($dia = 0; $dia < $n_personas; $dia++) {
$dia_num = $dia + 1;
echo <<<FIN
<table>
<caption>Dí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