Voy a adentrarme ahora en lo que se conoce por
combinatoria, exponiendo ejemplos sencillos y clásicos de esta rama de las matemáticas discretas.
23 - Variaciones con repeticiónLo primero que voy a hacer es poner un ejemplo:
Si quisiéramos hallar todas las variaciones con repetición en secuencias de 3 de este array:
string[] valores = {"a", "b", "c", "d", "e"};
Obtendríamos el siguiente resultado:
a a a
a a b
a a c
a a d
a a e
a b a
a b b
a b c
a b d
a b e
...
...
e e a
e e b
e e c
e e d
e e e
El orden de la complejidad temporal sería un equivalente a N
M, siendo N la cantidad de elementos y M el tamaño de la secuencia. Esto es deducible de la posibilidad de por cada espacio de la secuencia (M), en este caso 3, se pueden poner (N), en este caso 5 posibles elementos. Por lo tanto sería 5 * 5 * 5 = 5
3.
Veamos el código:
//Variaciones con repetición de N elementos en M
/// <summary>
/// Método portal
/// </summary>
static void VariacionesConRepeticion(string[] original, int size)
{
VariacionesConRepeticion
(original,
new string[size
],
0); }
static void VariacionesConRepeticion(string[] original, string[] variacion, int pos)
{
if (pos == variacion.Length)
{
Print(variacion); //Llama al método Print(), el cual lo que hace es imprimir un array en pantalla.
Console.WriteLine();
}
else
{
for (int i = 0; i < original.Length; i++)
{
variacion[pos] = original[i];
VariacionesConRepeticion(original, variacion, pos + 1);
}
}
}
Primero que todo, veamos que utilizamos un método portal, el cual recibe el array (en este caso es de
string para facilidad, pero se puede hacer de cualquier otro tipo incluso lo pueden implementar para que el método sea genérico). Lo otro que recibe es el tamaño de la variación (M) (M<=N) (N -> Cantidad de elementos).
En el método portal llamamos al método recursivo pasándole como parámetro el array
original, un array "
variacion" vacío con longitud M y una variable "
pos" para iterar sobre este array "
variacion"
Ahora, veamos, como todo método recursivo, tenemos una condición de parada que se cumplira cuando la variable "
pos" (la cual itera sobre "
variacion") sea igual al
Length del array "
variacion" (o lo que es lo mismo, que ya se ha haya rellenado ese array). En este caso, ya tenemos una variación completa, por lo tanto lo que haremos será Imprimirla en pantalla (lo que se haga puede variar de acuerdo al problema que estemos tratando de resolver.
Para imprimirlo en pantalla, utilizamos un método:
static void Print<T>(T[] array)
{
for (int i = 0; i < array.Length; i++)
{
if (i == array.Length - 1)
Console.Write(array[i]); //Imprimimos el elemento del array es el último elemento
else
Console.Write(array[i] + " "); //Imprimimos el elemento del array más un espacio si no es el último elemento
}
}
Ahora, en caso de que no se cumpla la condición de parada significa que todavía estamos "armando" la variación.
Para armar tenemos un ciclo
for, que recorre el array "
original", y lo que hacemos es asignarle al array "
variacion" en la posición "
pos" (que itera sobre "
variacion") el valor del array original en la posición
i (itera sobre el array "
original" utilizando el ciclo
for.
Luego lo que hacemos es llamar recursivo pasándole al método el array "original", "variacion" y la variable "
pos" incrementada en 1 (pos + 1), ya que pusimos un elemento en el array y ahora vamos a poner otro en la siguiente posición.
Voy a poner un ejemplo:
Imaginen el array "
original" como había dicho:
string[] valores = {"a", "b", "c", "d", "e"};
Y ahora, el array "
variacion" estaría así en un principio
[ ] | [ ] | [ ]
O sea, vacío
[ a ] | [ ] | [ ] - pos = 0
[ a ] | [ a ] | [ ] - pos = 1
[ a ] | [ a ] | [ a ] - pos = 2
Luego se retorna la llamada y entonces pos=3, aquí se imprime la variación pues ya está completa. Luego el ciclo
for camina y entonces la próxima asignación que se hace es:
[ a ] | [ a ] | [ b ] - pos = 2
Espero esto se haya entendido.
Si tienen alguna duda pregunten, pues esto a veces es enredado para verlo si no se ha visto alguna vez y/o no entienden bien la recursividad. Sobre todo, también es algo difícil explicarlo así en plan texto.
Seguimos con combinatoria (espero hayan entendido el anterior, pues no explicaré tan a fondo debido a la similitud24 - Variaciones sin repeticiónEste algoritmo es algo parecido, simplemente que no vamos a repetir elementos en cada variación.
Lo primero que voy a hacer es poner un ejemplo:
Utilicemos el mismo array que teníamos en el código anterior:
string[] valores = {"a", "b", "c", "d", "e"};
Si quisiéramos hallar todas las variaciones sin repetición en secuencias de 3 de este array obtendríamos:
a a a
a b c
a b d
a b e
a c b
a c d
a c e
a d c
a d b
a d e
...
...
e a c
e a d
e a b
El orden de la complejidad temporal sería un equivalente a N!/(N-M)!, siendo N la cantidad de elementos y M el tamaño de la secuencia. Esto es deducible de la posibilidad de por cada espacio de la secuencia (M), en este caso 3, se pueden poner (N-1), este caso 4 elementos posibles en la próxima posición, y después en la próxima (N-2), y asi sucesivamente, por lo que quedaría algo como: 5*4*3 = 5*(5-1)*(5-2) = 5!/(5-3)! = N!/(N-M)!
Primero voy a explicar un método que vamos a utilizar aquí. Utilizaremos un método para hacer
Swap entre dos elementos. Este método ya lo había explicado anteriormente en otro código, pero este tiene dos peculiaridades diferentes, primero que lo hice genérico para mostrar esto, y segundo que hace el intercambio pero de las referencias.
Este es el código:
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
Primero explico la palabra clave (
keyword)
ref. Esta palabra clave a un argumento causa que el argumento sea pasado al método por referencia y no por valor. El efecto de pasar un argumento por referencia implica que cualquier cambio que se realice al parámetro dentro del método es reflejado en el argumento en el método desde cual fue llamado.
Para llamar a un método pasándole un argumento por referencia se haría algo así:
static void Main(string[] args)
{
int numberOne = 1;
Inc(ref numberOne);
Console.WriteLine(numberOne); //El valor que se imprimirá será 2
}
public static void Inc(ref int number)
{
number++;
}
Ahora, que el método sea genérico, implica que se utilizará un
placeholder, dentro de todo el método para las operaciones con este tipo de datos dentro del método. Se podrá utilizar el método con cualquier tipo de dato siempre que no cause error en tiempo de ejecución de acuerdo a la función que se realice con él. Genéricas pueden ser clases, estructuras, interfaces y métodos.
Esto es una forma EXTREMADAMENTE lazy de explicarla, recomiendo ir a la MSDN para leer sobre esto.
Una vez visto, solo resta decir sobre este método que funciona intercambiando las referencias de las variables.
Ahora veamos el método como tal:
//Variaciones sin repetición de N elementos en M
/// <summary>
/// Método portal
/// </summary>
static void VariacionesSinRepeticion(string[] original, int size)
{
VariacionesSinRepeticion(original, size, 0);
}
static void VariacionesSinRepeticion(string[] original, int size, int pos)
{
if (pos == size)
{
Print(original, size);
Console.WriteLine();
}
else
{
for (int i = pos; i < original.Length; i++)
{
Swap(ref original[pos], ref original[i]);
VariacionesSinRepeticion(original, size, pos+1);
Swap(ref original[pos], ref original[i]);
}
}
}
Primero que todo démonos cuenta que es bastante parecido al otro método (
VariacionesConRepeticion()). Tenemos el método portal y el método recursivo, pero vemos que solo trabajamos sobre un array, pues por eso utilizamos un método
Swap para hacer intercambio de valores (que después lo volvemos a intercambiar para ponerlos en la posición original. Tenemos la condición de parada que se cumple cuando "
pos" sea igual al tamaño (M) de la variación que viene dado por la variable "
size"
Ahora, hay un pequeño cambio en el ciclo
for, y es que el ciclo
no empieza con la variable
i en 0, sino que empieza con el valor de "
pos". Y se hace un Swap antes del llamado recursivo y uno después, el cual pone los valores en la posición anterior a cambiarlo. Igual que en el método anterior se llama recursivo incrementando la variable "
pos"
Veamos un ejemplo utilizando el siguiente array y calculando las variaciones con tamaño 3:
string[] letras = { "a", "b", "c" };
Como trabajamos sobre le array "
original", el mismo estaría así al principio:
[ a ] | [ b ] | [ c ] - i= 0 y pos = 0
[ a ] | [ b ] | [ c ] - i= 0 y pos = 1
[ a ] | [ b ] | [ c ] - i= 0 y pos = 2
[ a ] | [ b ] | [ c ] - i= 0 y pos = 3 (Se cumplió la condición de parada y por lo tanto se tiene una variación, se imprime)
Luego, cuando se retorne el llamado tenemos a pos = 2 e i = 2 y cuando se incremente en el ciclo no se va a cumplir la condición del ciclo, va a terminar y va retornar la llamada, donde tendremos a pos = 1 e i = 1. Aquí ahora se va a incrementar i, pues va a cumplirse la condición del ciclo y tendremos a pos = 1 e i = 2, y por lo tanto se va a hacer el
Swap y va a quedar así:
[ a ] | [ c ] | [ b ] - i= 2 y pos = 1
Y después de se cumplirá la condición de parada y tendremos la variación lista. Así es prácticamente el funcionamiento del algoritmo, les recomiendo que le hagan un
Debug Step-By-Step para entenderlo mejor.
Nota: Como ven en ningón momento tenemos una variación en un array nuevo, si nuestro problema requiere devolver esta variación debemos hacer una copia del array original a uno nuevo copiando "
size" elementos.
string[] destino
= new string[size
]; Array.Copy(original, destino, size);
25 - CombinacionesPrimero que todo, veamos un ejemplo:
Si quisiéramos hallar todas las combinaciones posibles de secuencias de 5 de este array:
string[] valores = {"a", "b", "c", "d", "e"};
Obtendríamos:
a b c d e
En caso de que quisiéramos hallarlas en secuencias de 3, obtendríamos:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
Consideremos cada secuencia un subconjunto del conjunto original (el
array valores). Cada uno de estos subconjuntos son diferentes dos a dos.
Llamemos "combinaciones" a todas las formas posibles de tomar un subconjunto de elementos de un conjunto con un tamaño predefinido donde ninguno de estas formas son iguales y cada subconjunto no repite elemento.
Nota: Tengan en cuenta que vamos a utilizar el método
Print() que declaramos y utilizamos arriba (
Variaciones con repetición)
Como en casos anteriores vamos a tener un método portal, al cual le pasaremos como parámetro el array con los elementos. Ambos métodos los declaré genéricos. Repito, para entender mejor cómo funciona la genericidad de parámetros les recomiendo ir a la MSDN
/// <summary>
/// Método portal
/// </summary>
static void Combinaciones<T>(T[] letras, int m)
{
Combinaciones
(letras,
new T
[m
],
0,
0); }
Esté método recibe como parámetro el
array con los elementos y un
int que representa el tamaño de las combinaciones a buscar. Este
int debe ser menor o igual que la cantidad de elementos del
array. Por lo tanto les recomiendo que hagan una validación a este parámetro en el método portal.
El método recursivo recibe 4 parámetros, dos
array y dos
int. El primer
array es el original, el segundo es el
array para ir creando cada combinación, por lo tanto lo que se le pasa es un
array nuevo con tamaño igual al
int que recibió el método portal (
new T[m]]. Ahora, los
int que recibe son para iterar sobre los
array original y
combinacion respectivamente.
Luego, veamos el código del método recursivo:
static void Combinaciones<T>(T[] original, T[] combinacion,
int posOriginal, int posCombinacion )
{
if (posCombinacion == combinacion.Length)
{
Print(combinacion); //Imprimimos la combinación
Console.WriteLine(); //Hacemos un salto de linea en la consola
}
else if (posOriginal == original.Length)
return;
else
{
combinacion[posCombinacion] = original[posOriginal];
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion + 1);
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion);
}
}
En este método lo primero que hacemos es establecer las condiciones de parada (para la recursividad).
La primera es si se completó una combinación, por lo tanto vemos que la variable que itera sobre el
array combinacion llego a la longitud del
array. En tal caso, imprimimos la combinación.
La segunda condición es si ya se utilizaron todos los elementos originales en las combinaciones que antecedían con un elemento fijo.
Veamos un ejemplo de cómo funcionaría la otra parte del código:
Supongamos que el array original es:
string[] original = {"a", "b", "c", "d", "e"};
Antes de que se ejecute la línea:
combinacion[posCombinacion] = original[posOriginal];
Tendremos el
array combinacion:
[ null ] | [ null ] | [ null ]
Luego:
[ a ] | [ null ] | [ null ]
Luego se ejecutará el llamado recursivo:
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion + 1);
Y despues tendremos esto:
[ a ] | [ b ] | [ null ]
[ a ] | [ b ] | [ c ]
Y al llamar recursivo se cumplirá la primera condición de parada pues ya tenemos la primera combinación. Luego al salir de la recursividad, se llama recursivo de nuevo:
Combinaciones(original, combinacion, posOriginal + 1, posCombinacion);
Pero esta vez solo incrementamos la variable que itera sobre el array original. Por lo tanto esa variable estará apuntando al elemento (
d) del array original
Y tras hacer:
combinacion[posCombinacion] = original[posOriginal];
Tendremos:
[ a ] | [ b ] | [ d ]
Luego:
[ a ] | [ b ] | [ e ]
Y Luego se cumplirá la segunda condición de parada, por lo tanto saldremos de la recursividad hasta que la variable que itere por el
array combinacion este sobre el elemento 1.
Todo ira funcionando de esa manera.
Espero que se entienda, es un poco enredado, pero una vez que le hagas un
step-by-step debug lo entenderán.
Luego continúo con los códigos.
Salu2s
Mostrar Mensajes
)!