Muchas veces para resolver algunos problemas, necesitamos saber cuantas formas posibles hay de escribir un número, una palabra. A través de los algoritmos de combinaciones podemos resolver muchos problemas, que no podemos hacer facilmente con una calculadora, o con la mente. Por ejemplo, de cuantas formas posibles se puede descomponer un número en sumandos? De cuantas formas posibles podemos combinar ciertas letras? Este tipo de problemas son los que trataremos en este post.

Primero veremos y comentaremos el algoritmo que nos permite saber cuantas combinaciones posibles se pueden hacer con ciertas letras.

Veamos el código:

public static void Combina(string s)
{
        //Iniciamos este array auxiliar para
        //marcar los caracteres que ya combinamos
	bool []marcas = new bool[s.Length];
        //Llamamos al método recursivo
	Combina(s, "", marcas);
}
 
static void Combina(string original, string combinado, bool[]marcas)
{
        //Imprimimos la combinación si ya cambiamos
        //todas las letras una vez
	if(original.Length == combinado.Length)
		Console.WriteLine(combinado);
 
	for(int i = 0; i < marcas.Length; i++)
	{
           //Vemos si está marcada para no volverla a combinar
	   if(!marcas[i])
	   {
                //Marcamos el caracter que vamos a combinar
		marcas[i] = true;
                //Invocamos al metodo recursivo añadiendo
                //un caracter al string que combinamos
		Combina(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 este post. Espero les halla servido de ayuda este problemita, con esto podrá por ejemplo, saber de cuantas formas posibles se pueden combinar las letras a, n y c.

Si 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…

En el proximo post, veremos entonces todas las permutaciones que podemos hacer para descomponer un número en sumandos.

dudas=> comentarios