Número mínimo de bits necesarios para almacenar el orden de una baraja

Question

Supongamos que tengo un mazo de cartas barajado (52 cartas, todas normales, sin comodines) Me gustaría registrar el orden en mi ordenador de tal manera que el pedir requiere el menor número de bits (no estoy contando las tablas de búsqueda ect como parte del trato, sólo el ordenamiento en sí.

Por ejemplo, podría grabar un conjunto de cadenas en la memoria:

"ocho de tréboles", "nueve de diamantes"

pero eso es obviamente una tontería, más sensatamente podría dar a cada tarjeta un número entero (sin signo) y simplemente registrarlo...

17, 9, 51, 33...

que es mucho mejor (y creo que sería alrededor de 6 bits por número por 53 números así que alrededor de 318 bits), pero probablemente todavía no es ideal.. para empezar no tendría que registrar la última tarjeta, llevándome a 312 bits, y si sé que la penúltima tarjeta es una de las dos opciones entonces podría bajar a 306 bits más un bit que fuera verdadero si la última tarjeta fuera el valor más alto de las dos tarjetas restantes y falso en caso contrario....

Podría hacer otros giros y trucos, pero también sospecho que esta es una rama de las matemáticas donde hay una respuesta elegante...

Answer 1

Como dice carlop, se puede almacenar el número de orden en 226 bits. Luego, para encontrar el orden de las cartas, divide el número de orden entre 51!. El cociente es el número de tarjeta de la primera tarjeta y el resto es el número de orden de las 51 tarjetas restantes.

Añadido: Si sólo se almacena un número de tarjeta (0-51) para cada posición, se necesitan 6 bits por tarjeta, para un total de 312 bits. Cuesta menos de 100 bits y es más fácil de desempaquetar. El enfoque anterior supone que se lleva la cuenta de las tarjetas utilizadas, así que después de haber hecho 20 tarjetas, se puede bajar a 5 bits, después de 36 se puede pasar a 4 bits, etc. En este caso se utiliza el 0 para la última carta, el 1 para la penúltima, el 2 para las dos siguientes, etc. 0+1+2*2+3*4+4*8+5*16+6*20=249 bits. Esto no supone un gran aumento respecto a lo mejor posible. El aumento se debe a que al almacenar el número de la ordenación se aprovechan los datos desperdiciados al utilizar 6 bits para elegir uno de 40, por ejemplo.

Answer 2

Hay $52!$ posible ordenación de las 52 cartas. Cada bit puede almacenar 2 valores, por lo que hay que encontrar el más pequeño $n$ para lo cual $2^n\geq52!$ , $n\geq log_2(52!)$ Es decir $226$ .

El algoritmo para reconstruir la ordenación a partir del número es el sugerido por Ross Millikan.

Answer 3

Como señalan las otras respuestas, puedes codificar las permutaciones de varias maneras, pero necesitarás al menos 226 bits (en promedio). Para leer sobre esquemas de codificación concretos, puedes empezar aquí