Notas de Combinatoria
Notas Elementales de Combinatoria
En el siguiente archivo ".pdf" puedes encontrar los principios básicos de combinatoria así como diversas técnicas de conteo. También puedes checar las fórmulas de combinatoria, permutaciones, principio de las casillas, binomio de Newton combinaciones con repetición entre otros. Te sugerimos que le "eches un vistaso" a estas notas antes de proseguir con la página
Pensemos que tenemos un diamante, un rubí, una esmeralda. ¿Cuántos subconjunto podemos formar con estos 3 elementos? Un problema típico en combinatoria, consiste en formar todos los subconjuntos que un conjunto de n elementos. En nuestro ejemplo se tiene un total de 8 subconjuntos si incluimos el vacio.
| Conjunto | Representación Binaria |
|
Æ
diamante rubí esmeralda; diamante, rubí diamante, esmeralda; rubí, esmeralda diamante, rubí y esmeralda |
0 0 0
1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 |
En la primera columna hemos anotado todos los subconjuntos (incluyendo el vacio) y en la segunda, una interpretación, con un número binario, para su respectivo conjunto. La primera cifra, del número binario, refiere al primer elemento (al diamante en nuestro caso). Si el primer elemento esta presente entonces el primer número es uno, de lo contrario lo marcamos como un cero. Del mismo modo, la segunda cifra refiere al segundo elemento y así sucesivamente. Para nuestro caso, se tiene un número de tres cifras, una cifra por cada elemento, por lo tanto tenemos 23 = 8 combinaciones posibles. En general si se tiene un conjunto de n elementos, se tiene un total de 2n subconjuntos diferentes. Para darse cuenta de ello, basta recordar el principio multiplicativo de combinatoria y observar que en cada cifra tenemos siempre 2 opciones (el cero y el uno).
De lo anterior, podemos transformar nuestro problema original a formar todos los números binarios de n cifras. Por lo tanto, debemos desarrollar un algoritmo que sea capaz de formar todos los números binarios.
| Algoritmo Recursivo |
|
Para formar todos los números binarios de n cifras, ocupamos un arreglo de enteros Array de largo N. La idea es formar un árbol tal que, en la iteración Pos marquemos la posición Pos del Array con un 0 y mandemos a llamar a la función recursivamente con un paso más. De igual modo, luego marcamos con un 1 la posición Pos de Array. El proceso se detiene cuando Pos es igual a N. Entonces se manda a procesar el arreglo Array. |
void Binarios(int *Array,int N,int Pos)
{
// Checamos si tenemos formado un número binario.
if( Pos == N )
{
Procesa(Array,N);
return;
}
// Marcamos con 0 la posicion Pos y mandamos a llamar
// a la función con un paso más.
Array[Pos] = 0;
Binarios(Array,N,Pos+1);
// Marcamos con 1 la posicion Pos y mandamos a llamar
// a la función con un paso más.
Array[Pos] = 1;
Binarios(Array,N,Pos+1);
}
|
| Algoritmo Iterativo |
|
Para este caso empleamos solo el largo N y emplearemos un arreglo Array local y una variable Pos. Primero inicializamos el arreglo Array con ceros, después sumamos uno a la primera cifra (Array[0]) y hacemos el "acarreo" de cifra a cifra. Es decir, si una cifra en la posición Pos es igual a 2, entonces anotamos un cero en esa posición y sumamos uno a la siguiente cifra. Por ejemplo en base diez, si sumamos 145 + 361 = 506. Para sumar primero sumamos las unidades (5+1=6), después las decenas (4+6 = 10) pero como da 10 entonces ponemos un cero en las decenas y "llevamos uno" a las centenas. De igual modo en base 2, cuando alguna cifra suma 2 o más, entonces hay un "acarreo" de cifras. El proceso se repite hasta que Pos sea igual a N, en ese momento hemos recorrido todos los números binarios de N cifras. |
void Binarios(int N)
{
int *Array,Pos,i;
// Pedimos memoria.
Array = new int[N+1];
// Inicializamos.
for(i = 0; i < N+1; i++)
{ Array[i] = 0; }
Pos = 0;
// Mientras no estemos fuera del arreglo.
while(Pos < N)
{
// Procesamos el arreglo binario.
Procesa(Array,N);
// Iniciamos Pos y aumentamos a la primera cifra.
Pos = 0;
Array[Pos]++;
Pos++;
// Mientras la cifra en la posición anterios (Pos-1)
// sea igual a 2, lo hacemos 0 y aumentamos en uno
// a la siguiente cifra.
while( Pos < N && Array[Pos-1] == 2)
{
Array[Pos-1] = 0;
Array[Pos]++;
Pos++;
}
}
// Liberamos la memoria.
delete[] Array;
}
|
Estadísticas
Última actualización:
Por Marte Ramírez