Algoritmo de permutaciones sin repeticion

Question

Hola Ramón, la pregunta es facil. Se podria hacer un algoritmo que coja 4 elementos y los combine de todas las formas posibles sin que se repita ningun resultado? Supongo que hay que saber bastantes matematicas para eso, si me pudieras dar alguna pista te lo agradeceria, porque me gustaria hacerme un programita para uso propio que lo haga. Un saludo. Edito: no confundir elementos con numeros. Por ejemplo sacar las combinaciones del 1,2,3,4 que son 4 elementos. En la pregunta original puse numeros y queria decir elementos con lo cual en vez de numeros podria ser cualquier cosa. Mientras ves la pregunta y si te animas a contestar estoy buscando soluciones. Se me ocurre que quiza haya alguna funcion predefinida en algun lenguaje que lo haga, si hay funciones que te sacan el pi o la raiz cuadrada puede que ya haya alguna para esto. He descubierto, de momento, que lo que busco se llama permutaciones sin repeticion y que su formula es n!, con lo cual para el ejemplo que he puesto de 4 elemento seria 4x3x2x1=24 combinaciones posibles sin que se repita ningun numero. Solo me falta desarrollarlo un poco, pero creo que no tiene que ser muy dicicil hacer un algoritmo que lo haga. Aunque si ya hay algo prefabricado mejor ;)

Answer 1

Algoritmo como tal no me suena que exista.

Para hacer lo que sugieres yo haría una pila con los cuatro elementos. Luego for anidados que vayan desapilando (o una recursiva si te animas). Jugaría con el apilamiento y el desapilamiento para conseguir no repetir ningún número (o elemento) y sacar todas las combinaciones. Es decir, seguiría una estructura de árbol para recuperar la posición al llegar al nodo hoja y sacar la siguiente combinación.

Mira a ver si te sirve :)

Comments

Bueno, algo he conseguido. He creado un código válido sólo para 4 elementos, que es lo que yo necesitaba.
Tengo la espinita que cuando pongo determinados caracteres no funciona. Por ejemplo '€' me da una cosa rara.

Está en PHP y no está muy bien escrito, pero me funciona. Tengo que pulir lo de ciertos caractéres, pero por lo demás bien. El error lo da la función reverse que no traduce bien ese caracter.

 

<?php
 
$input=array('€','€','€','€');

$resultado=permutar($input);
for($f=0;$f<count($resultado);$f++){
	echo $resultado[$f];
	echo "<br>";
}

/*******************************************************/
function permutar($input)
{
$miarray = array();
$cadena="";
//copio el array
$temporal=$input;
//borro el primer numero del array


array_shift($input);
//ahora la cuenta esta en que solo quedan 3
for($u=0;$u<count($temporal);$u++)

{


for($i=0;$i<count($input);$i++)
{

array_push($input,$input[0]);
array_shift($input);


for($e=0;$e<count($input);$e++)
{
	$cadena.=$input[$e];
	
}



array_push($miarray,$temporal[$u].$cadena);
array_push($miarray,$temporal[$u].strrev($cadena));
$cadena="";

}
array_shift($input);
array_push($input,$temporal[$u]);

}
return $miarray;
}
 
 
?>

 

---

No veo la función reverse.

Si es un String no debería de darte problemas. Si tienes problemas con los Strings te recomiendo que uses comillas simples y no dobles en PHP (ya que las dobles se evaluan, y puede que te den problemas)

---

Gracias por la ayuda Ramón, como esto era un pequeño desvío de mi proyecto personal de crear una app, pues no voy a entredar mucho, arreglaré lo de los caracteres especiales y lo dejaré estar. No me compensa gastar tiempo en esto.

La función reverse es una propia del lenguaje PHP, concretamente: strrev();

Por supuesto que lo puedo arreglar creando una personalizada, pero lo dejo estar por ahora.

Pego unas imágenes para que se vea el resultado con unas pruebas que hice, espero que le sirva a alguien en un futuro.

La primera columna son los caracteres que me dan error, la segunda un grupo de letras

'ABC','DEF','GHI','JKL' y la tercera las letras A,B,C,D. Como se ve se realizan las 24 combinaciones posibles, sin entrar en el string, sino tratándolo como un bloque de 4 elementos diferentes

 

---

A vale, lo que te ocurre es un problema de caracteres típico de programación Web por los formatos. Simplemente pon en el PHP la codificación de caracteres UTF-8 como con:

header('Content-Type: text/html; charset=utf-8');

y si generas HTML pon en el Head la misma codificación:

<head>
    <meta charset="UTF-8">
    <!--Otra manera: <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -->
</head>

Y en nombre de la comunidad de desarrolladores gracias por la solución. Seguro que ayuda a mucha gente :D

---

buenas amigo y como haria si lo necesito para 3 caracteres? lequiero uno al array pero  me repite siempre uno... te dejo una imagen

---

Asegúrate que cuando eliminas el elemento del array no se esté eliminando de una copia del array. Si estás utilizando PHP prueba por ejemplo con la función array_pop() que desapila el último elemento del array (http://php.net/manual/es/function.array-pop.php)

---

Puedes crear un nuevo array sin los repetidos con:

//crea un nuevo array con valores unicos de otro array

$newarray=array_unique($miarray);