Generando permutaciones en C#

Sep 6, 2009 Codigos C# 26 comentarios

Muchas veces para resolver algunos problemas, necesitamos saber cuantas ordenaciones posibles tiene una lista de numeros o caracteres.

A través de los algoritmos de permutaciones podemos responder muchos problemas que no podemos hacer tan facilmente con la mente. Por ejemplo, cuantas palabras podemos formar con las letras ‘a’, ‘b’ y ‘c’? Este tipo de problemas son los que trataremos en este post.

Primero veremos y comentaremos el algoritmo que nos permite generar todas las permutaciones posibles se pueden hacer con ciertas letras.
Nota: No es difícil adaptar este código para que funcione con arrays de números (sería un buen ejercicio)

Veamos el código:

public static void Permuta(string s)
{
        //Iniciamos este array auxiliar para
        //marcar los caracteres que ya combinamos
	bool []marcas = new bool[s.Length];
        //Llamamos al método recursivo
	Permuta(s, "", marcas);
}
 
static void Permuta(string original, string permutacion, bool[]marcas)
{
        //Imprimimos la combinación si ya cambiamos
        //todas las letras una vez
	if(original.Length == permutacion.Length)
		Console.WriteLine(permutacion);
 
	for(int i = 0; i < marcas.Length; i++)
	{
           //Vemos si está marcada para no volverla a permutar
	   if(!marcas[i])
	   {
                //Marcamos el caracter que vamos a permutar
		marcas[i] = true;
                //Invocamos al metodo recursivo añadiendo
                //un caracter al string que permutamos
		Permuta(original, permutacion + original[i], marcas);
                //Desmarcamos el caracter para poder usarlo
                //en otras combinaciones
		marcas[i] = false;
	   }
	}
}

Como ven es un algoritmo muy sencillo, y no tan largo, donde usamos la técnica de backtracking, o vuelta atrás, que vimos hace un tiempo en Recursividad y backtracking. Espero les halla servido de ayuda este algoritmo.

Por ejemplo, para saber cuáles son las permutaciones que se pueden formar con las letras a, b y c hacemos algo así:

Permuta("abc");
Console.ReadLine();

esto es lo que devolvería el programa:

abc
acb
bac
bca
cab
cba

Ya se encargarán ustedes de buscarle las aplicaciones que lleva, también pueden tratar de hacer este algoritmo un poco más eficientes, piensen un poco en el como…

Dudas en los comentarios

Compartir:

26 comentarios

Forma parte de nuestra discusión y síguela de cerca

Exelente amigo, lo cale y corre bastante bien :D

solo algo, en la parte de lo de adentro del for se me hizo algo extraña y me marco error:

for(int i = 0; i < marcas.Length; i++)

lo que hice fue cambiarle un poco para que dejara de marcar el error dejandola asi y corrio bien.

for(int i = 0; i < marcas.Length; i++)

Autor: jOefaY | Fecha: Oct 28, 2009.

JOefaY:
Si, parece que el interprete que uso, tenía algún error e interpretó el signo ‘<‘ como ‘<’.

Autor: Tomy | Fecha: Nov 25, 2009.

esta bueno el asuntillo gracias por explicarlos

Autor: alex | Fecha: Jun 2, 2010.

genial aportacion mi estimado, me ayudara a implementar algo de cifrado por transposicion, espero mostrar el codigo pronto. Gracias! Saludos..

Autor: Pedro | Fecha: Oct 12, 2010.

ALGUIEN TIENE EL METODO DE TRANSPOSICIÓN EN C?

Autor: SOLEDAD | Fecha: Oct 17, 2010.

hola grax por el aporte pero tengo una duda en el for:

for(int i = 0; i < marcas.Length; i++)

que es o significa esto : &lt

si puedes explecalo te lo agradecere mucho XD y grax!!!

Autor: Baka | Fecha: Oct 28, 2010.

&lt es el símbolo “< “, lo que pasa q a veces el interprete que uso no funciona como debería :D
saludos

Autor: Tomy | Fecha: Feb 25, 2011.

Necesito el codigo para poder resolver el siguiente problema:
tengo numeros de 1 al 45 y necesito coger combinaciones de 6 que sea en orden o en desorden o viseversa puedes ayudarme cone l codigo.

Autor: ywca25 | Fecha: Ago 17, 2011.

Perdon me exprese mal, pero necesito esas combinaciones, alguien me puede brindar el código?

Autor: ywca25 | Fecha: Sep 6, 2011.

Gracias Eitol, ya está corregido, hablamos de permutaciones no combinaciones :D

Autor: Tomy | Fecha: Sep 8, 2011.

Amigo, es esta parte

Permuta(original, combinado + original[i], marcas);

no me detecta que es “original”, y no se donde lo declaras

Autor: Israel Calderón | Fecha: Oct 29, 2011.

HOla, quise probar el codigo pero este pedazo:

Permuta(original, combinado + original[i], marcas);

la variable combinado no la toma, por q nunca la definis y tampoco me doy cuenta q queres decir con esa variable.
como hago?

Autor: samsung | Fecha: Oct 30, 2011.

@Israel: El método que debes llamar es Permuta(“cadena a permutar”). El string original en este caso es “cadena a permutar”. Como paso el string directamente como parámetro no es necesario declararlo antes, ya que el string no es necesario inicializarlo.

@samsung: El método que debes llamar para permutar un string es el anterior, el segundo método es private, solo debes llamar Permuta(“cualquier cosa”). De todas formas puedes ver que combinado si se inicializa como la cadena vacía “” cuando se llama al segundo método desde el primero, y esa variable se utiliza para ir guardando cada combinación para no perder la cadena original que se quería permutar.

Autor: Tomy | Fecha: Oct 31, 2011.

Excelente el código me ha parecido fenomenal la verdad no entiendo muy bien como esta pero de que hace lo que tiene que hacer no hay duda. Una pregunta se puede hacer si en vez de permutar una cadena quisiéramos permutar los elementos de un array de enteros.

Gracuas de antemano

Autor: Manuel Paz Robles | Fecha: Nov 13, 2011.

Hola, felicidades por el blog. Soy muy pero muy nuevo en programación. Mi línea de investigación es la biología y ahora estoy aplicando muchos modelos ecológicos por medio de simulaciones generadas por computador. Este código que pusiste me sirve para generar una permutaciones de combinaciones de sistema. Sin embargo no se como usarlo. Lo intenté usar en mi IDE de embarcadero para C++ pero me da un error en la primera línea. La verdad no se como ponerlo en el IDE y como usarlo. Sería mucha molestia si me guiaran al respecto?
gracias de antemano por esto
suerte

Autor: Madset | Fecha: Abr 24, 2012.

@Manuel: La verdad habría q hacer algunos pequeños cambios, pero no es muy complicado, ya que en C# ve los string como un array de char, lo único q no puedes hacer es combinado + original[i], porque el operador + no esta definido en la clase Array ;)
@Madset: El problema es que el código está escrito en C#, y hay algunas diferencias, aunque no es muy complicado traducirlo a C++

Autor: Tomy | Fecha: Abr 26, 2012.

¿de donde bajaste el programa para hacer estas permutaciones?? si me das el link te lo agradeceria mucho…
SALUDOS

Autor: Felipe_VargasS | Fecha: Abr 28, 2012.

@Felipe, este código lo escribí cuando estaba en primer año de la carrera… de hecho me costó bastante trabajo ;)

Autor: Tomy | Fecha: May 2, 2012.

no entiendo el funcionamiento de “combinado”. lo quiero correr en un programa que estoy implementando y no se como solucionarlo.

Autor: aguztin | Fecha: May 5, 2012.

Si me dices que error te da el programa podré ayudarte ;)

Autor: Tomy | Fecha: May 8, 2012.

no me reconoce “combinado”

Autor: aguztin | Fecha: May 8, 2012.

ah, disculpa fue un error mío… en vez de “combinado” es “permutacion”, que es el nombre de la variable donde voy guardando la permutación actual… ya lo arreglé en el código, saludos y gracias :D

Autor: Tomy | Fecha: May 14, 2012.

Hola, podrías convertir la función a iterativa? . Saludos

Autor: nacho | Fecha: Jun 23, 2013.

excelente codigo , me salvaste la vida , estoy siguiendolo paso a paso , y me sorprendo , esto es lo que andaba buscando , ahora lo estoy pasando a numero , o a colecciones , muchas gracias.

Autor: Dario | Fecha: Nov 25, 2014.

Gracias por tu trabajo… El cual me resulta de gran ayuda para resolver un problema que tengo que es una especie de extencion de tu trabajo.. en el cual necesito que el string de entrada pueda ser:
1ro. “abcdABCD” y que me los permute todos
2do En la impresion por pantalla yo le pueda limitar que sean mostrados solo las permutaciones de 3 o 4 etc… a mi necesidad en cada caso… Es muy complicado pedirte que modificar para hacerlo..???

Gracias de nuevo.

Autor: Luis E Guzman | Fecha: Jul 5, 2015.

Gracias por tu trabajo.. El cual me resulta de gran ayuda para resolver un problema que tengo que es una especie de extencion de tu trabajo.. en el cual necesito que el string de entrada pueda ser:
1ro “abcdABCD”… que me los permute todos..
2do En la impresion por pantalla .. yo le pueda limitar a que solo me muestre las permutaciones de 3 o 4 etc.. segun mi necesidad en cada corrida. seria muy complicado y trabajoso el pedirte cuales modificaciones serian necesarias para que tu trabajo se adaptara a lo solicitado en mi caso..????

Gracias mil.

Luis e. Guzman

Autor: Luis E Guzman | Fecha: Jul 5, 2015.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.