problema recursividad

[gustavoh10]

Gente como andan!
Tengo un problema que seguro es una pavada, pero la verdad
que nos esta poniendo los pelos de puntas a mi y a unos
amigos.
Paso a describir el inconveniente.
Tengo un lista de lugares en un array. Digamos
1 LSM
2 Crespo
3 Diamante
4 Paraná
5 Valle Maria

y quiero armar un arbol para que me quede de esta forma. (los
diferentes caminos posibles para recorrer las ciudades)

1 <-(punto de partida)
2 3 4 5
2 3 5 4
2 4 3 5
2 4 5 3
2 5 3 4
2 5 4 3
3 2 4 5
3 2 5 4
...
...
5 4 3 2

los número representan las ciudades por las que paso. Tendria
que armar todos los caminos posibles pasando solo una vez por cada
ciudad.
En este caso me quedan 24 caminos posibles

etc, etc...
La verdad que la unica forma que se nos ocurrio es haciendo
recursividad, pero estamos teniendo problemas para empezar.
Alguien podria darnos una patadita para poder empezar. jeje!!!
Gracias!

[DeeR]

Tu problema se puede resolver con Grafos dirigos o no dirigidos, para recorrer todos los grafos puedes usar un algoritmo en profundidad, ahora si quieres obtener todos los posibles caminos, creo que tendria que ser una variante del algoritmo de dijkstra.

Hay mucha info de la red sobre grafos (se tocan mucho en ramos como Algoritmos y Estructuras de Datos). en fin cuando tu ya tenga la base teorica y los peseudocodigos(algoritmos) sobre grafos, podrias comenzar a aplicarlo en php (o buscar directamente como representar grafos en php) lo mejor siempre ha sido el autoaprendizaje


Saludos

[gustavoh10]

gracias, voy a investigar sobre los grafos y despues te cuento como me fue.
Gracias

[gustavoh10]

Lo que necesito es un algoritmo que realice las diferentes combinaciones que existen entre los elementos.
Alguien sabe si hay una funcion de php que lo realice.

DeeR, estube viendo sobre grafos y me di cuenta que no necesito nada complicado, solo a partir de un array generar todas las posibilidades.
Con lo que me decis seguro que lo puedo sacar, pero me parece mas facil buscar algo ya hecho q calcule las combinaciones.
gracias!

[gustavoh10]

Gente encontre lo que necisitaba en otra seccion del foro (javascript)

www-forosdelweb.com/showthread.php?t=183178&highlight=permutaciones

gracias!!!

[DarioDario]

No sé si te servirá de algo ahora... pero hice lo que querías de dos formas distintas (solo por aburrimiento ). Acá te las paso por si lo quieres ver:

Esta es sin recursividad:

Código PHP:

  $ciudades = array(2 => 'Crespo', 3 => 'Diamante', 4 => 'Parana', 5 => 'Valle Maria');

foreach($ciudades as $num1 => $algo)
{
        foreach($ciudades as $num2 => $algo)
        {
                if($num2 == $num1)
                   continue;

                foreach($ciudades as $num3 => $algo)
                {
                        if($num3 == $num2 or $num3 == $num1)
                           continue;

                        foreach($ciudades as $num4 => $algo)
                        {
                                if($num4 == $num3 or $num4 == $num2 or $num4 == $num1)
                                   continue;

                                echo $num1.' '.$num2.' '.$num3.' '.$num4.'<br>';
                        }
                }
        }
}  
   

Y esta es con una función recursiva:

Código PHP:

  $ciudades = array(2 => 'Crespo', 3 => 'Diamante', 4 => 'Parana', 5 => 'Valle Maria');

function recorrido($ciudades, $recorrido)
{
        if(count($ciudades) == 0)
        {
                foreach($recorrido as $c1 => $n1)
                        echo $c1.' ';
                echo '<br>';
                return TRUE;
        }

        foreach($ciudades as $c => $n)
        {
                $ciudades2 = $ciudades;
                $recorrido2 = $recorrido;
                $recorrido2[$c] = $n;
                unset($ciudades2[$c]);
                recorrido($ciudades2,$recorrido2);
        }
}

recorrido($ciudades,array());  
   

Saludos y cualquier cosa si no entendes pregunta y te explico.

[gustavoh10]

Uhh que maestro, mil gracias por molestarte.
Voy a probar lo que hiciste, porque la solucion que encontre esta en
javascript, ya lo pase a php, pero voy a ver lo que hiciste.
La solucion en javascript me sirvio para empezar, pero encuentra
todas las combinaciones con repetición.
1 1 1 1
1 1 1 2
1 1 1 3
1 1 1 4
1 1 2 1
.....
y lo que necesito es que me encuentre todos las combinaciones sin
repetición.

lo que habia pensado es realizarlo de la siguiente forma.
supongamos que tengo
2 3 4 5
ir moviento el ultimo elemento hacia atraz.
2 3 5 4
2 5 3 4
2 5 4 3
2 4 5 3
2 4 3 5
2 3 4 5 <-- repetido. pongo en el comienzo el segunto elemento

3 2 4 5
3 2 5 4
3 5 2 4
....
y asi.....

[gustavoh10]

DarioDario, probe tu solución, ande de 10 mil gracias y gracias de nuevo por molestarte.

Saludos!!!

[DarioDario]

Iniciado por gustavoh10

DarioDario, probe tu solución, ande de 10 mil gracias y gracias de nuevo por molestarte.

Saludos!!!

Me alegro de que te sirva, pero la idea es que no lo uses a ciegas e intentes comprender como trabajan ambos casos. El primero es el mas fácil y el mas desprolijo.... el segundo es más lindo pero de todas maneras sigue siendo "tosco" no esta optimizado y hay muchas otras formas de hacer lo mismo pero de forma diferente.
Te invito a que intentes hacer un función recursiva distinta para este problema... así practicaras y si te surgen dudas puedes venir a preguntar.

Saludos.

[gustavoh10]

Si, lo mire, y le hice reformas... ahora arma un array por cada camino posible y lo inserta en otro array para formar una matriz..

Gracias!

[charlynovoa]

Buenas espero que esten como para ayudarme y retomar el tema..
yo lo que andaba necesitando es un script en php que recorra todas sus posibilidades
de una matriz dada, sea x * x , ...
un ejemplo básico sería .. en una matriz de 2 * 2...
sería:

0 - 0
0 - 0

1 - 0
0 - 0

0 - 1
0 - 0

0 - 0
1 - 0

0 - 0
0 - 1

1 - 1
0 - 0

1 - 0
1 - 0

1 - 0
0 - 1

0 - 1
1 - 0

0 - 1
0 - 1

0 - 0
1 - 1

1 - 1
1 - 0

1 - 0
1 - 1

0 - 1
1 - 1

1 - 1
0 - 1

1 - 1
1 - 1

un script que recorra y liste todas esas posibilidades...
si fuese una matriz de 3*3 serían (3*3)*(3*3) la cantidad de posibilidades... pero ya se entendio el concepto...
por favor si alguien puede darme una mano se los agradeceria muchisimo

Saludos !
Charly

[vevni]

jojjojjjoo miranadamas aqui viendo de nuevo a mi cuate dariodario, que onda.....
ejejej quisas no me recuerdes, soy de cancun, recuerdo cuando diste unas clases de expresiones regulares por el irc... saludos.... que tiempos, jejejee