que - Programación para cuadros jóvenes.

que es la etiqueta head y body

Question

Una pregunta extraña sigue:
Estoy haciendo una competencia de resolución de problemas en mi escuela y nos permiten usar una computadora. Como soy el único en la competencia que sabe cómo codificar, uso los programas C y Pascal para resolver problemas más rápido. Lo he hecho con ejercicios de pseudocódigo a código, algoritmos, verificación de conjeturas de Collatz y demás.
Ahora, ayer estaba entrenando para el próximo desafío (18 de abril), y vi un ejercicio sobre los cuadros jóvenes. Fue redactado así (haré todo lo posible para traducir del italiano):
"Los diagramas de Ferrers son configuraciones de N cajas distribuidas en una o más filas horizontales, alineadas a la izquierda y configuradas de modo que cada fila contenga un número igual o menor de cajas que la fila sobre esta. Estas configuraciones también se pueden describir en una lista de Número de cajas, como en esta imagen:
diagramas de ferrers http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_m_07a_400.jpg
Un cuadro joven es un diagrama de Ferrers de N cajas llenas de números enteros de 1 a N. Ejemplo:
tablones jóvenes http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_s_03b_400.jpg
Si los números en los cuadros se ordenan de modo que estén en orden creciente por fila y por columna, la tabla es "estándar" (ejemplo: primer, tercer y quinto cuadro). En cuadros estándar, la primera casilla de la primera fila siempre contiene 1. N está siempre en la casilla de la izquierda en una de las filas del diagrama.


PROBLEMA

Considere un diagrama de [6,3,2,1,1,1] de Ferrers:
1) Si 6 está fijo en la sexta casilla de la 1ª fila y 11 está fijo en la última casilla de la 1ª columna, ¿de cuántas maneras puede completar el diagrama de una manera estándar?

2) Si 7 está fijo en la sexta casilla de la 1ª fila y 11 está fijo en la última casilla de la 1ª columna, ¿de cuántas maneras puede completar el diagrama de una manera estándar?

3) Si 8 está fijo en la sexta casilla de la 1ª fila y 11 está fijo en la última casilla de la 1ª columna, ¿de cuántas maneras puede completar el diagrama de una manera estándar?

He intentado codificar una solución con una matriz rellena con esos números y con "-1" como un "carácter de final de fila", pero me quedé atascado. ¿Cómo puedo codificar "rellenarlo de todas las formas posibles para que el cuadro sea estándar?".

Answer 1

Aquí hay una solución de ejemplo que usa SWI-Prolog para el primer problema:

:- use_module(library(clpfd)).

tableau(Ts) :-
        Ts = [[A,B,C,_,_,F],
              [G,H,I],
              [J,K],
              [L],
              [M],
              [N]],
        A = 1,
        maplist(ascending, Ts),
        ascending([A,G,J,L,M,N]),
        ascending([B,H,K]),
        C #< I,
        append(Ts, Vs),
        all_different(Vs),
        Vs ins 1..14,
        F = 6,
        N = 11,
        label(Vs).

ascending(Vs) :- chain(Vs, #<).

La respuesta es que hay 2 formas de completar el cuadro:

?- tableau(Ts), maplist(writeln, Ts).
[1,2,3,4,5,6]
[7,12,13]
[8,14]
[9]
[10]
[11]
    Ts = [[1, 2, 3, 4, 5, 6], [7, 12, 13], [8, 14], [9], [10], [11]] ;
[1,2,3,4,5,6]
[7,12,14]
[8,13]
[9]
[10]
[11]
    Ts = [[1, 2, 3, 4, 5, 6], [7, 12, 14], [8, 13], [9], [10], [11]] ;
false.

Answer 2

Este es un problema de programación de lógica de restricción. Usa el lenguaje de programación Prolog. Prólogo de Sicstus con la biblioteca clpfd.

Teniendo en cuenta el diseño como tal:

ABCDEF
GHI
JK
L
M
N

--Código--

use_module(library(clpfd)).

all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N]),
domain([A,B,C,D,E,F,G,H,I,J,K,L,M,N],1,14),
B #> A, C #> B, D #> C, E #> D, F #> E,
G #> A, H #> B, H #> G, I #> G, I #> H,  I #> C,
J #> A, J #> G, 
L #> A, L #> G, L #> J,
M #> A, M #> G, M #> J, M #> L,
N #> A, N #> G, N #> J, N #> L, N #> M.

A=1
F=6
N=11

Answer 3

Para resolver esto usaría la Programación de Restricciones (CP). El cuadro joven es en realidad uno de los problemas estándar que trato de resolver al aprender un nuevo sistema de PC. Aquí hay una lista de las implementaciones hasta ahora: http://hakank.org/common_cp_models/#youngtableaux .

He cambiado el modelo "simple" de MiniZinc con algunas restricciones adicionales para sus preguntas específicas. Vea el modelo completo aquí: http://www.hakank.org/minizinc/young_tableaux_stack_overflow.mzn

(MiniZinc es de muy alto nivel y fácil de experimentar para problemas como este).

En pocas palabras acerca de la representación en el modelo: para un problema de tamaño n (partición de n), los cuadros se representan como una cuadrícula ("x", tamaño n veces n) con los valores de 1 a n + 1, donde cada fila y la columna se clasifican en orden creciente; por lo que n + 1 se clasifica en último lugar y actúa como un valor vacío. La estructura de partición ("p") se maneja para cumplir con la estructura de Young / Ferrer (consulte el modelo para obtener más detalles).

Cada una de las tres preguntas tiene dos restricciones adicionales (en comparación con la formulación estándar del problema):

• un cierto número debe estar en la sexta casilla de la primera fila La restricción agregada es x [1,6] = 6% o 7 u 8

• y 11 debería estar en el último cuadro de la primera columna. Esto es un poco más complicado, pero mi camino es el siguiente, es decir, que en la primera columna 11 debería ser el último de los valores menores que n + 1, es decir, todos los valores que siguen en la columna son n + 1:

   exists(j in 1..n) (
        x[j,1] = 11 // forall(k in j+1..n) (x[k,1] = n+1)
   )

Entonces, si he entendido las preguntas correctamente, las respuestas son: 1) 2 soluciones 2) 10 soluciones 3) 30 soluciones

Answer 4

Sin usar un programa, creo que la respuesta a 1) es 2. Derivar esto a mano podría llevar a alguien a una solución algorítmica.

La primera fila comienza con 1 y termina con 6. Por lo tanto, los números que pueden ir a la fila 1 deben cumplir esta condición: 1 <x <6. De los 14 dígitos que pueden ingresar a este cuadro, solo 4 cumplen esa condición, y son: 2 3 4 5. Esto significa que la fila 1 debe ser: 1 2 3 4 5 6.

La primera columna comienza con 1 y termina con 11. Los números que pueden ir a la primera columna deben cumplir una condición similar: 1 <y <11. De los números restantes no asignados, solo 4 cumplen con esta condición: 7 8 9 10. Esto lleva a la primera columna siendo: 1 7 8 9 10 11.

Ahora solo quedan 3 números: 12 13 14. Solo hay dos formas de organizarlos en las 3 celdas restantes de los cuadros. Se pueden arreglar:

12 13

14

- o -

12 14

13

Al tratar de abordar esto en el código, uno podría ir por la ruta de la fuerza bruta o buscar técnicas de propagación de restricciones y de retroceso. Es por esto que alguien sugirió Prolog antes. Otro lenguaje para mirar sería Python.