Generando permutaciones en C#

Sep 6, 2009 Codigos C# 16 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 resolver muchos problemas, que no podemos hacer facilmente con una calculadora, o con la mente. Por ejemplo, cuantas contraseñas se pueden generar con 3 números y 5 letras? 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.

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, combinado + 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, saber de cuantas formas posibles se pueden permutar las letras a, n y c?

Hacemos algo así:

Combina("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 => comentarios

Compartir:

Relacionados

algunos artículos que te pueden interesar
Codigos PHP, Jquery, CSS, .NET

16 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.

Muy chulo tu codigo.. pero – a juzgar por el ejemplo – eso son PERMUTACIONES y no COMBINACIONES

Autor: fulano | Fecha: Nov 23, 2009.

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

fulano:
Tienes razón, el metodo devuelve todas las permutaciones, pero puse combinaciones para no tener que explicar entonces, que cosa son las variaciones sin repetición, con repetición, combianciones, permutaciones, etc. Combinaciones suena más natural verdad?

Autor: Tomy | Fecha: Nov 25, 2009.

esta bueno el asuntillo gracias por espicarlos

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.

Disculpa pero esas son permutaciones. En las combinaciones el orden no importa, solo la existencia de determinados elementos en el subgrupo

Autor: Eitol | Fecha: Sep 6, 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.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.