Orden lexicográfico de combinaciones matemáticas en C#.

Aquí se presenta un algoritmo en C# para obtener el índice lexicográfico de una combinación de elementos y vice-versa (una combinación a partir de su índice lexicográfico).

"Los coeficientes binomiales o combinaciones indican el número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado." (wikipedia)

Ejemplo:

Se tiene un conjunto con 6 objetos diferentes {1,2,3,4,5,6}, de los cuales se desea escoger 2 (sin importar el orden de elección). Existen 15 formas de efectuar tal elección.

C(n,k) = n! / k! (n - k)!   =>   C(6,2) = 15

A continuación se listan estas 15 formas, en orden lexicográfico:
(1,2) (1,3) (1,4) (1,5) (1,6)
(2,3) (2,4) (2,5) (2,6)
(3,4) (3,5) (3,6)
(4,5) (4,6)
(5,6)

Así, por ejemplo, la séptima combinación en orden lexicográfico es la (2,4).

Podría decirse que el orden lexicográfico está dado por la tasa de cambio entre los elementos. Por ejemplo el elemento (1,3) difiere en sólo una unidad con respecto a (1,2), y es lexicográficamente el número 2. Así, el número de cambios y la posición del elemento cambiado definen de alguna manera el orden lexicográfico.

Sea n la cantidad de objetos de los que se puede elegir y k la cantidad de objetos que se eligen, el algoritmo que se presenta a continuación, generará un arreglo de elementos (una combinación) a partir del valor del índice lexicográfico i.

O sea, el método retornará el vector (2,4), con las entradas n=6, k=2, i=7.

public static int[] GetOrderedSetByIndex(int n, int k, int i)
{
    if (k == 1) return new int[] { i };
    int[] arr = new int[k];
    int r, m = 0;
    for (int j = 0; j < k - 1; j++)
    {
        arr[j] = (j != 0) ? arr[j - 1] : 0;
        do
        {
            arr[j]++;
            r = choose(n - arr[j], k - (j + 1));
            m = m + r;
        } while (m < i);
        m = m - r;
    }
    arr[k - 1] = arr[k - 2] + i - m;
    return arr;
}

NOTA: El método choose no se lista pero se puede descargar el código completo desde aquí.

Para el ejemplo anterior, la llamada al método que obtiene la combinación (2,4) sería: GetOrderedSetByIndex(6, 2, 7)



De igual forma, se presenta el método inverso, para obtener el índice lexicográfico a partir de una combinación dada:

public static int GetIndexByOrderedSet(int n, int k, int[] comb)
{
    int[] C = new int[k];
    long LI = 0, R;
    for (int i = 1; i <= k - 1; i++)
    {
        C[i - 1] = 0;
        if (i != 1)
            C[i - 1] = C[i - 2];
        do
        {
            C[i - 1] = C[i - 1] + 1;
            R = combine(n - C[i - 1], k - i);
            LI = LI + R;
        } while ((C[i - 1] < comb[i - 1]));
        LI = LI - R;
    }
    return (int)LI + comb[k - 1] - comb[k - 2];
}

NOTA: El método combine no se lista pero sólamente calcula el coeficiente binomial. El código completo se puede descargar desde aquí.

Para el ejemplo anterior, la llamada al método que obtiene el índice lexicográfico sería: GetIndexByOrderedSet(6, 2, new int[] { 2, 4 }); y retornaría 7.



Estos métodos son útiles también para listar lexicográficamente todas las combinaciones dados un valor de n y k, como se muestra a continuación:

for (int i = 1; i <= combine(6, 2); i++)
{
    int[] comb = GetOrderedSetByIndex(6, 2, i);
    Console.WriteLine("({0},{1})", comb[0], comb[1]);
}

El código completo se puede bajar desde aquí.
Espero que alguien le sea útil.

Federico D. Colombo NOTA:
Los algoritmos presentados aquí están basados en el Algoritmo 515 de Buckles.


Vínculos:

http://msdn.microsoft.com/en-us/library/aa289166.aspx
http://saliu.com/lexicographic.html
http://www.calculatorsoup.com/calculators/discretemathematics/combinations.php