Combinatoria e ID

Question

Estoy trabajando en un proyecto y este es un problema matemático que me he encontrado. La combinatoria no es mi punto fuerte, así que agradecería cualquier ayuda.

La idea es que tienes 81 elementos para elegir y eliges 6 de ellos, sin repeticiones, el orden sí importa. Sé entonces que el número de combinaciones que se pueden elegir es $$\frac{81!}{(81-6)!}=233‚668‚955‚520$$ Hasta ahora no ha habido ningún problema. Ahora quiero dar a cada uno de ellos una idea numérica de 1 a casi 234.000 millones en función de su "orden". Así que comenzando con el más bajo siendo 1, el segundo más bajo 2, etc. Obtendríamos

1-2-3-4-5-6 = 1

1-2-3-4-5-7 = 2

1-2-3-4-5-8 = 3

...

1-2-3-4-5-81 = 75

1-2-3-4-6-5 = 76

y así sucesivamente de forma similar. Donde sube de manera similar una y otra vez más y más a la izquierda hasta que finalmente termina con

81-80-79-78-77-76=233‚668‚955‚520

Mi problema es que soy totalmente incapaz de encontrar una buena fórmula para conseguirlo. Estoy buscando una fórmula $$f:\mathbb{N}_{81}^6\to\mathbb{N}$$

tal que $$f(a,b,c,d,e,f)=\text{id}$$

¿Hay alguna forma de averiguarlo o tengo que utilizar otros métodos?

Answer 1

En Python, en menos de 20 líneas de código:

def perms(n, m):
    result = 1
    for i in range(0, m):
        result *= (n - i)
    return result

def id(alphabet, numbers):
    head = numbers[0]
    index = alphabet.index(head)
    m = len(numbers)
    if m == 1:
        return 1 + index 
    p = perms(len(alphabet) - 1, m - 1)
    alphabet.remove(head)
    numbers.remove(head)
    return index * p + id(alphabet, numbers)

def fun(a, b, c, d, e, f):
    # alphabet goes from 1 to 81
    alphabet = [i for i in range(1, 82)]
    numbers = [a, b, c, d, e, f]
    return id(alphabet, numbers)

print(fun(1,2,3,4,5,6))
print(fun(1,2,3,4,6,5))
print(fun(81,80,79,78,77,76))
print(fun(23,80,49,26,15,11))

El código se imprime:

1
77
233668955520
66299919067

El código es recursivo. Básicamente, encuentra el índice del alfabeto del primer símbolo de la permutación. A partir de ahí, calcula el número de permutaciones que empiezan con símbolos anteriores en el alfabeto. Además, añade el índice de la permutación con su primer símbolo eliminado en un alfabeto con el mismo símbolo eliminado también.

Si necesitas código en algún otro lenguaje de programación, házmelo saber.

(Fíjate en el error que tienes en la línea: 1-2-3-4-6-5=76; debería ser 77)