algorithm - trucos - Maneras eficientes de ordenar una baraja de cartas reales
probabilidad de una baraja de 52 cartas (6)
Creo que contar ordenadamente junto con su enfoque de ordenación por inserción podría funcionar bien: busque las unidades y colóquelas primero, luego las de dos y así sucesivamente.
Esto puede parecer mucho trabajo ya que sus tarjetas están numeradas de 1 a más de 200, pero creo que en este caso todo será mucho trabajo. Puede acelerar las cosas haciendo varias tarjetas a la vez, lo que no debería ser demasiado difícil: busque las unidades, dos y tres (y más si está preparado para ello) todo al mismo tiempo, y colóquelos en las posiciones correspondientes ( combinando con "orden de inserción" para que no tenga que dejar un espacio vacío entre las tarjetas).
A menudo tengo que ordenar los mazos de cartas. Estas son tarjetas de "coleccionista" numeradas del 1 al 216 y hay números dobles y faltantes.
Estoy buscando algoritmos de clasificación que funcionen bien con tarjetas físicas. El orden de inserción parece correcto porque insertar una tarjeta no requiere un cambio de las tarjetas subsiguientes como en la memoria de una computadora. Sin embargo, escanear a través de una cubierta grande requiere mucho tiempo. Con una plataforma grande, hay incluso posibilidades de que puedas dejarla y tener que reiniciar la clasificación.
Podría dibujar las tarjetas en una mesa grande y colocar directamente cada tarjeta en su ubicación correcta, pero esto requiere bastante espacio y no es muy conveniente.
Mi enfoque habitual es hacer un primer escaneo a través de la cubierta y colocarlos en las pilas 1-49, 50-99, 100-149, 150-199, 200+. Luego escaneo cada mazo y los pongo en las pilas 0, 1, 2, 3, 4. Y, finalmente, aplico una ordenación por inserción en cada paquete de 10 unidades. Esto sigue siendo un proceso tedioso sin embargo.
Otra idea es tomar las 50 pilas y ordenarlas aproximadamente. 25 irían por el medio, 40 en algún lugar cerca del final de la pila y así sucesivamente. Eso trae rápidamente un 50-deck aproximadamente ordenado y puedo escanearlo fácilmente y corregir la clasificación.
Me preguntaba si un algoritmo más sofisticado podría aplicarse convenientemente a una plataforma física. No veo cómo podríamos aplicar una ordenación rápida y cosas como la ordenación de pilas requieren conocer el índice de la tarjeta dentro de la baraja.
Creo que una especie de tipo rápido es la forma más fácil para esto. Creo que incluso hubo algunos videos de Youtube que muestran a las personas que hacen esto con una baraja de póquer normal.
Atraviesas la baraja y colocas todas las cartas más pequeñas que 100 en una pila izquierda, todas más grandes en una pila derecha. Luego retrocede a través de las pilas, primero la profundidad (para que no tenga demasiadas pilas a la vez). En algún umbral (quizás alrededor de 5 cartas), simplemente ordena "en mano" (similar a la ordenación por inserción, tal vez). Finalmente, apila las pilas juntas.
También puede hacer una clasificación de fusión: divida la pila en dos, recise la profundidad primero, hasta que llegue a dos pilas de 5 cartas cada una. Ordena estas dos pilas "en la mano", luego colócalas boca arriba una al lado de la otra. Combínelos en una pila de resultados colocando siempre la más baja de las tarjetas mostradas en la pila de resultados. Puedes ver qué pilas ya están ordenadas al dejarlas boca arriba. Asegúrese de siempre fusionar pilas de tamaño similar, de lo contrario proceda a dividir la siguiente pila sin clasificar.
Edición: la clasificación de radix también podría ser buena: coloque las tarjetas en diez pilas por su último dígito, apile estas pilas juntas en orden. Luego, ponga las tarjetas en diez pilas por su segundo a último dígito, apílelas nuevamente en orden. Finalmente, póngalos en pilas por su tercer a último dígito (según su descripción, que es el primer dígito), y apílelos juntos, listo. Esto podría ser lo más fácil, después de todo, y es O (n) (necesitas tres pases a través de la cubierta).
Eric
No estoy seguro de si todavía te encuentras en el orden de las barajas físicas de cartas, pero estaba investigando esto (clasificaciones de cartas, clasificaciones de agujas, clasificando machiens, etc.) y me topé con tu publicación. Si no lo hace, entonces espero que a alguien más le resulte útil / útil.
Si tiene la capacidad de usar un perforador y modificar un borde de la baraja de cartas, se puede usar una técnica de clasificación para ordenar la pila completa en las operaciones log2 (# de cartas). Así que se necesitarían 8 operaciones para ~ 200 tarjetas.
Una forma que encontré funcionó bien es la siguiente:
1.) Ordene el mazo de la forma que desee y asigne un # a cada carta.
2.) Convierta este # a binario en una longitud de log2 (# de tarjetas). por ejemplo, log2 (216) ~ 8, entonces solo necesitarías 8 lugares ... entonces 0x0 se convertiría en 00000000
3.) Enode cada tarjeta con su representación binaria como la imagen de abajo
Foto
4.) Recorte los 1 como se muestra en la tarjeta 1 a continuación (la derecha o LSB se recorta) la segunda a la última en la tarjeta 2 también se recorta ...
5.) Agarre un clavo, una aguja de tejer o un perchero recto, etc. ... empaque la plataforma (desordenada) con los agujeros alineados
6.) inserte la aguja a través del orificio derecho en toda la plataforma (o el lsb en binario). levante la aguja y deje que las tarjetas que no tienen anillo en esa pestaña (usted la corta) caigan dentro de una caja. Mueve las cartas enganchadas en la aguja al frente de la baraja. ** NO CAMBIE EL ORDEN DE LAS TARJETAS NO SELECCIONADAS AL LEVANTAR LAS TARJETAS SELECCIONADAS ... p. Ej., Mantenga la baraja en una caja de tarjetas de ajuste holgado o algo similar
7.) Vuelva a juntar la plataforma, esta vez use la aguja en el orificio adyacente utilizado anteriormente (el segundo a la derecha). haga lo mismo, deje que las tarjetas sin adjuntar / no seleccionadas caigan en una caja y repita.
8.) w / 8 operaciones toda la cubierta debería estar ordenada ... Espero que esto ayude a alguien
así es como funciona: la primera operación (paso 6) mueve todos los intgers impares al frente, por ejemplo, pone 1 delante de 2, 3 delante de 4, etc.
La segunda operación se mueve (1/2 en frente de 3/4), y 5/6 en frente de 7/8. tercera operación mueve 1/2/3/4 frente a 5/6/7/8 y 9/10/11/12 frente a 13/14/15/16 .. cuarta operación mueve 1/2/3/4 / 5/6/7/8 frente a 9/10/11/12/13/14/15/16/16 / etc ... el último movimiento toma ~ la mitad del mazo y lo coloca frente al otro. .. y da como resultado un mazo completamente ordenado en una cantidad mínima de movimientos
Saludos, Jeremy
He impartido clases universitarias que a veces son muy amplias, y he practicado con la tarea similar de clasificar exámenes graduados. Casi siempre uso el tipo de cubo, como tú. También mencionas un enfoque de clasificación de combinación, que a veces también hago, pero solo ahorra tiempo cuando comienzas con subpiles ordenados, no con un juego de cartas totalmente revuelto.
Hay trucos para acelerar el orden del cubo. Gran parte del tiempo en una clasificación de cubo humano se emplea calculando el cubo para el siguiente elemento. Puedes probar dos trucos. En primer lugar, puede agrupar ordenadas por dígitos, lo que supongo que se denomina clasificación de radix, para que nunca tenga que comparar números. La primera etapa utiliza tres cubos, que no son muchos pero podrían estar bien. La segunda etapa es el trabajo "principal", con diez cubos. En la tercera etapa, usted está clasificando diez tarjetas numeradas y el sentido común sugiere una ordenación por inserción. Pero incluso para esa etapa, una clasificación de radix podría acelerar las cosas, incluso aunque cada cubeta solo obtenga una carta. Por supuesto, no debe usar "cubos" con cuatro lados, sino simplemente pilas de cartas sobre una mesa. Solo utilizaría el método de cubo para el dígito de las unidades si es fácil barrer las tarjetas en orden. Posiblemente para la etapa intermedia, una ranura con tres lados funcionaría mejor que una pila abierta de cartas.
Un segundo truco es etiquetar las ubicaciones en la tabla del 0 al 9 para que pueda encontrar la pila correcta más rápidamente. Las etiquetas se pueden pegar en la mesa para que pueda reutilizarlas.
No estoy seguro de si esta estrategia particular de clasificación de cubo es la mejor. El punto es que la clasificación de cubetas es el método más común para clasificar los exámenes parciales, y probablemente también sea el mejor para grandes barajas de cartas. Hay varias variaciones para probar y debes experimentar un poco para ver cuál funciona mejor.
La razón por la que pregunto sobre el número total real y el tamaño es que si el área total de todas las cartas posibles es lo suficientemente pequeña, puede ser posible simplemente: ir a través de la baraja colocándolas todas en una cuadrícula, y cada una de las cartas es correcta Spot, y luego simplemente recogerlos en orden.
Por ejemplo, si hubiera un máximo de 100 tarjetas, numeradas del 1 al 100, imagine que su superficie de trabajo está dividida en una cuadrícula rectangular de 10 x 10; luego, a medida que se procesa cada tarjeta, coloque, por ejemplo, la tarjeta 67 en la séptima columna de la sexta fila. Una vez que todas las cartas están dispuestas, recogerlas en orden.
Esto solo funciona si su superficie de trabajo es lo suficientemente grande como para contener todas las cartas, pero si son del tamaño normal de una carta y tiene una mesa grande y bonita, debería poder manejar los 200 que menciona, especialmente porque puede superponerse fácilmente. Las ''celdas'' y el método siguen funcionando.
Para mí, este es el enfoque que más utiliza el hecho de que se trata de un problema en el espacio físico, en lugar de en bits: cada objeto físico se procesa solo dos veces (una vez para colocarlo, una para recogerlo), porque Para un algoritmo que involucra objetos físicos, moverlos tiene un costo mucho mayor que pensar qué hacer .
Me encontré con este post porque quería ordenar rápidamente una baraja regular de 52 cartas. Un poco de experimentación sugiere que puedo clasificar todo el mazo en aproximadamente 1:30 usando el algoritmo de repartir cada carta en una pila para cada palo y luego hacer la inserción ordenar un palo a la vez (casi sin práctica, por lo que estoy seguro Se puede hacer más rápido con la práctica).
Intenté algunos enfoques diferentes, incluyendo hacer una división rojo-negro y luego dividir más a los rojos y negros en sus propios trajes, luego hacer la inserción ordenada por el juego, pero esto fue notablemente más lento. También intenté dividir cada palo en 2-7,8-A para ver si el orden de inserción realizado en grupos más pequeños de cartas fue más rápido, pero también fue notablemente más lento. Así que mi retiro es no perder el tiempo con una recursión excesiva para hacer el cubo.
Al extrapolar este método a sus tarjetas, parece que el mejor método es repartir las tarjetas en cubos de un tamaño que sea fácil de clasificar de una vez (10 o 20 tarjetas tal vez, ya que es fácil descubrir qué cubo tienen). entrar) luego hacer la inserción de ordenación en los cubos. Presumiblemente, deberías poder ordenar tus 216 mazos de cartas en aproximadamente 6-7 minutos de esta manera.