ヤングテーブルウのプログラミング

Question

奇妙な質問は次のとおりです。
私の学校では競技の解決に問題があり、私たちはコンピュータを使用することができます。私はコード作成方法を知っている唯一の競争相手だから、問題をより早く解決するためにCとPascalプログラムを使用します。私は擬似コードからコードへの演習、アルゴリズム、Collat​​zの憶測の検証などでこれを行ってきました。
昨日、私は次のチャレンジ（4月18日）のために練習していました。私はヤング・テーブルローの運動を見ました。
"Ferrersダイアグラムは、1つ以上の横の行に分散されたN個のボックスの構成で、左揃えで構成され、すべての行に等しいかそれ以下のものが含まれるように構成されています（イタリア語からの翻訳には最善を尽くします）
ferrers diagrams http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_m_07a_400.jpg
ヤングtableauは、1からの整数で満たされたN個の箱のFerrers図です。この図のように、箱の数のリストで記述することができます。 N.例：
young tableaux http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_s_03b_400.jpg
ボックス内の数字が行と列で昇順にソートされる場合、テーブルは「標準」です（例：第1、第3、第5テーブル）。標準tableauxの場合、最初の行の最初のボックスには常に1が含まれます.Nは常にダイアグラムの行の1つ左のボックスにあります。図6は、1行目の6箱に固定されており、11が中に固定されている場合）
1：


PROBLEM

[6,3,2,1,1,1] Ferrersの図を検討最初の列の最後のボックスで、標準的な方法でいくつの方法で図を完成させることができますか？

2）最初の列の6番目のボックスに7が固定され、1番目の列の最後のボックスに11が固定されている場合、標準的な方法でいくつの方法で図を完成できますか？

3）最初の列の6番目のボックスに8が固定され、1番目の列の最後のボックスに11が固定されている場合、標準的な方法でいくつの方法で図を完成できますか？

I '私はこれらの数字と "行末の文字"として "-1"でいっぱいの行列を持つソリューションをコード化しようとしましたが、私は立ち往生しました。 ？」。プログラムを使用せずに

Answer 1

、私は1への答えを信じて）手でこれを導出2.あるアルゴリズムの解に誰かを導くかもしれない。

最初の行は1から始まり、そこで6で終了可能な数x < 6.このテーブルに入ることができる14桁のうち、その条件を満たすのは4桁だけです：2 3 4 5.これは、行1が次のものでなければならないことを意味します。1 2 3 4 5 6.

最初の列は1で始まり、11で終わります。最初の列に入る数値は、同様の条件を満たす必要があります。1 < y < 11.残りの未割り当て数のうち、わずか4 7 8 9 10 10.最初の列が次のようになります。1 7 8 9 10 11.

現在残っている数字は3つだけです：12 13 14.残りの3つの細胞は、この表色系のものである。

- または -

コードでこれに取り組むしようとすると、1が行くことができる：彼らを配置することができますブルートフォースルート、または制約の伝搬とバックトラッキング技術を調べることができます。これが誰かがPrologを早期に提案した理由です。見るべきもう一つの言葉はPythonだろう。

Answer 2

これは制約論理プログラミングの問題です。プログラミング言語のPrologを使用してください。 clpfdライブラリを持つSicstusプロローグ。などのレイアウトを考慮

：ここ

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

は、最初の問題のためにSWI-プロローグを用いて試料溶液である：

:- 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, #<). 

答えは、テーブルを完成させる2つの方法があるということです：

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

これを解決するには、Constraint Programming（CP）を使用します。新しいCPシステムを学ぶときに私が解決しようとする標準的な問題の1つです。ここまでの実装のリストはhttp://hakank.org/common_cp_models/#youngtableauxです。

私は、あなたの特定の質問にいくつかの特別な制約を加えて「プレーン」MiniZincモデルを変更しました。ここにフルモデルを参照してください： http://www.hakank.org/minizinc/young_tableaux_stack_overflow.mzn

（MiniZincは非常に高いレベルと、このような問題のためで実験するのは簡単です。）モデルでの表現についてのショート

：サイズnの問題（パーティション用 ボックスは、1からn + 1までの値を持つグリッド（ "x"、n倍のn倍）で表され、各行と列は昇順にソートされます。したがって、n + 1は最後にソートされ、空の値として動作します。パーティション構造（ "p"）はYoung/Ferrer構造に準拠するように処理されます（詳細はモデルを参照）。追加制約がある

• は、特定の数は、最初の行 の6ボックス内にすべきである：

  3つの質問のそれぞれは、（問題の標準製剤と比較して）2つの追加の制約を有していますX 6％又は7又は8

• 及び11は、第1の列 の最後のボックスであるべき= [1,6]これは少し複雑ですが、私の方法は、本である、すなわち 最初の列にその11はn + 1より小さい値の最後でなければならず、すなわち、 列に以下のすべての値は、n + 1です：私が正しく質問を理解している場合

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

だから、答えは次のとおりです。 1）2つのソリューション 2）10のソリューション 3）30社のソリューションは、