La respuesta de Alexander Farrugia resuelve el problema maravillosamente, pero no pude resistir jugar un poco más, y aquí hay un pseudocódigo en caso de que sea útil para alguien. La implementación es simple y razonablemente eficiente. En particular, una buena propiedad de la función de decodificación es que evita el cálculo de cualquier binomio, y pasa solo una vez sobre las 24 bolas.
De bolas a número:
función codificar (bolas []) {
N = 0
para bola = 0..length (bolas) -1 {
N + = binomio (bolas [bola] -1, longitud (bolas) -bola)
}
devolver N
}
- ¿Por qué las computadoras no pueden programarse por sí mismas?
- ¿Es Python el mejor lenguaje de programación para las matemáticas aplicadas?
- ¿Qué libros de algoritmos y estructuras de datos tratan bien la recursividad?
- ¿Cómo se usa la teoría de juegos en la IA?
- Cómo mejorar mi habilidad de programación en los temas de matemática y geometría
Entonces, por ejemplo, encode([23,17,11,4]) = 7923 . El binomio (n, m) debería devolver 0 en caso de que m> n.
De número a bolas:
función de decodificación (N, bolasLeft, totBalls) {
resultado = ()
binom = binomial (totBalls, ballsLeft)
para b = totBalls..1 por -1 {
si binom <= N {
agregue b + 1 al resultado
N – = binom
binom = binom * ballsLeft / (b-ballsLeft + 1)
bolasIzquierda–
}
binom = binom * (b-ballsLeft) / b
}
}
Entonces, decode(7923, 4, 24) = [23,17,11,4] .
Si b es el número de bolas a codificar yn es el número total de bolas, entonces la codificación se realiza en O (b ^ 2), donde un factor b proviene del cálculo de los binomios, y la decodificación toma O (n).
Usando una búsqueda binaria, las asintóticas de la decodificación se pueden cambiar a O (b ^ 2 log n), pero eso sacrifica la elegancia del algoritmo y solo es útil si n es enorme en comparación con b.
