Programmazione per giovani tableaux

Question

Una domanda strana segue:
Sto facendo un concorso per la risoluzione dei problemi alla mia scuola e ci permettono di usare un computer. Dato che sono l'unico della concorrenza che sa come codificare, uso i programmi C e Pascal per risolvere i problemi più velocemente. L'ho fatto con esercizi di pseudocodice su codice, algoritmi, verifica della congettura di Collatz e così via.
Ora, ieri mi sono allenato per la prossima sfida (18 aprile) e ho visto un esercizio su Giovani tableaux. È stato formulato in questo modo (farò del mio meglio per tradurre dall'italiano):
"I diagrammi di Ferrers sono configurazioni di N scatole distribuite in una o più righe orizzontali, allineate a sinistra e configurate in modo che ogni riga contenga un numero uguale o inferiore numero di caselle oltre la riga su di esso Queste configurazioni possono anche essere descritte da un elenco del numero di caselle, come in questa immagine:
ferrers diagrams http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_m_07a_400.jpg
Un tableau giovane è un diagramma di Ferrers di N caselle riempite con numeri interi da 1 a N. Esempio:
young tableaux http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_s_03b_400.jpg
Se i numeri nelle caselle sono ordinati in ordine crescente per riga e per colonna, la tabella è "standard" (esempio: primo, terzo e quinto tableau). tableaux, la prima casella della prima riga contiene sempre 1. N è sempre nella casella più a sinistra in una delle righe del diagramma.


PROBLEMA

consideri un [6,3,2,1,1,1] diagramma Ferrers:
1) Se 6 è fissato al 6 ° casella della prima fila e 11 è fissato in l'ultima casella della prima colonna, in quanti modi è possibile completare il diagramma in un modo standard?

2) Se 7 è fissato sulla sesta casella della prima riga e 11 è fissato nell'ultima casella della prima colonna, in quanti modi è possibile completare lo schema in modo standard?

3) Se 8 è fissato sulla sesta casella della prima riga e 11 è fisso nell'ultima casella della prima colonna, in quanti modi è possibile completare lo schema in modo standard? "

I ' Ho provato a codificare una soluzione con una matrice piena di quei numeri e con "-1" come "carattere di fine riga", ma mi sono bloccato. Come posso codificare "riempirlo in ogni modo possibile in modo che il tableau sia standard ?".

Answer 1

senza utilizzare un programma, credo che la risposta a 1) è 2. Derivando questa mano potrebbe portare qualcuno a una soluzione algoritmica.

la prima riga inizia con 1 e termina con 6. Pertanto i numeri che possono g o nella riga 1 deve soddisfare questa condizione: 1 < x < 6. Delle 14 cifre che possono entrare in questo tableau, solo 4 soddisfano tale condizione, e sono: 2 3 4 5. Ciò significa che la riga 1 deve essere: 1 2 3 4 5 6.

La prima colonna inizia con 1 e termina con 11. I numeri che possono andare nella prima colonna devono soddisfare una condizione simile: 1 < y < 11. Dei restanti numeri non assegnati, solo 4 soddisfare questa condizione: 7 8 9 10 10. Questo porta alla prima colonna: 1 7 8 9 10 11.

Ci sono solo 3 numeri rimanenti ora: 12 13 14. Ci sono solo due modi per organizzarli nel rimanenti 3 celle del tableaux.Essi possono essere organizzati:

- o -

Cercando di affrontare questo nel codice, si potrebbe andare il percorso della forza bruta, o vai a esaminare le tecniche di propagazione dei vincoli e backtracking. Questo è il motivo per cui qualcuno ha suggerito Prolog prima. Un altro linguaggio da guardare sarebbe Python.

Answer 2

Questo è un problema di programmazione della logica di vincoli. Utilizzare il linguaggio di programmazione Prolog. Prologo di Sicstus con la libreria clpfd.

Considerando il layout tale:

ABCDEF 
GHI 
JK 
L 
M 
N 

--Code--

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

Ecco una soluzione campione utilizzando SWI-Prolog per il primo 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 risposta è che ci sono 2 modi per completare il tableau:

?- 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 4

Per risolvere questo, vorrei utilizzare la programmazione di vincoli (CP). Il tableau Young è in realtà uno dei problemi standard che cerco di risolvere quando apprendo un nuovo sistema CP. Ecco un elenco delle implementazioni finora: http://hakank.org/common_cp_models/#youngtableaux.

Ho modificato il modello "semplice" MiniZinc con alcuni vincoli extra per le vostre domande specifiche. Vedere il modello completo qui: http://www.hakank.org/minizinc/young_tableaux_stack_overflow.mzn

(MiniZinc è molto alto livello e facile da sperimentare per problemi come questo.)

corta sulla rappresentazione nel modello: Per un problema di dimensione n (partizione di n), le caselle sono rappresentate come una griglia ("x", dimensionata n volte n) con i valori da 1 an + 1, dove ogni riga e colonna sono ordinate in ordine crescente; quindi n + 1 viene ordinato per ultimo e funge da valore vuoto. La struttura delle partizioni ("p") viene quindi gestita per conformarsi alla struttura Young/Ferrer (vedere il modello per i dettagli).

Ciascuna delle tre domande ha due vincoli aggiuntivi (rispetto alla formulazione standard del problema):

• un certo numero dovrebbe essere nel 6 ° casella della prima fila Il vincolo aggiunto è x [1,6] = 6% o 7 o 8

• e 11 dovrebbe trovarsi nell'ultima casella della prima colonna questo è un po 'più complicato, ma la strada è questa, cioè che nella prima colonna 11 dovrebbe essere l'ultimo dei valori inferiore a n + 1, , ad es.tutti i valori seguenti nella colonna sono n + 1:

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

Quindi, se ho capito correttamente le domande le risposte sono: 1) 2 soluzioni 2) 10 soluzioni 3) 30 Soluzioni