17

奇妙な質問が続きます。
私は学校で問題解決コンテストを行っており、コンピューターを使用することが許可されています。競技会でコーディングの仕方を知っているのは私だけなので、C と Pascal プログラムを使用して問題をより迅速に解決します。疑似コードからコードへの演習、アルゴリズム、コラッツ予想の検証などでそれを行いました。
さて、昨日、私は次の課題 (4 月 18 日) のトレーニングをしていて、Young タブローの演習を見ました。それは次のように表現されました（イタリア語から翻訳するために最善を尽くします）：
「Ferrers ダイアグラムは、1 つ以上の水平行に分散された N 個のボックスの構成であり、左揃えで、すべての行がその上の行と同じかそれよりも少ない数のボックスを含むように構成されています。これらの構成は、この画像のようなボックスの数: (ソース: olimpiadiproblemsolving.it ) 若いタブローは、1 から N までの整数で満たされた N 個のボックスの Ferrers ダイアグラムです。例: (ソース: olimpiadiproblemsolving.it )
フェラーズダイアグラム



若いタブロー


ボックス内の数字が行ごと、列ごとに昇順になるように並べ替えられている場合、テーブルは「標準」です (例: 1 番目、3 番目、5 番目のタブロー)。標準的なタブローでは、最初の行の最初のボックスには常に 1 が含まれます。N は常に、図のいずれかの行の左端のボックスにあります。


問題

[6,3,2,1,1,1] Ferrers ダイアグラムを考えてみましょう:
1) 1 行目の 6 番目のボックスに 6 が固定され、1 列目の最後のボックスに 11 が固定されている場合、標準的な方法で図を完成させますか?

2) 1 行目の 6 番目のボックスに 7 が固定され、1 列目の最後のボックスに 11 が固定されている場合、標準的な方法で図を完成させる方法はいくつありますか?

3) 1 行 6 番目のボックスに 8 が固定され、1 列目の最後のボックスに 11 が固定されている場合、標準的な方法で図を完成させる方法はいくつありますか?

」これらの数字と「-1」を「行末文字」として埋めた行列を使って、「タブローが標準になるように可能な限りすべての方法で埋めてください」とコーディングするにはどうすればよいですか?

4

5 に答える 5

4

これを解決するには、制約プログラミング (CP) を使用します。Young タブローは、実際、私が新しい CP システムを学習するときに解決しようとする標準的な問題の 1 つです。これまでの実装のリストは次のとおりです: http://hakank.org/common_cp_models/#youngtableaux .

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

(MiniZinc は非常に高レベルで、このような問題を簡単に試すことができます。)

モデルでの表現について簡単に説明します。サイズ n (n のパーティション) の問題の場合、ボックスは 1 から n+1 の値を持つグリッド (「x」、サイズは n × n) として表されます。ここで、各行はおよび列は昇順でソートされます。したがって、n+1 は最後にソートされ、空の値として機能します。パーティション構造 ("p") は、Young/Ferrer 構造に準拠するように処理されます (詳細については、モデルを参照してください)。

3 つの質問のそれぞれには、2 つの追加の制約があります (問題の標準的な定式化と比較して)。

  • 特定の数値は最初の行の 6 番目のボックスにある必要があります 追加される制約は x[1,6] = 6 % または 7 または 8 です

  • 11 は最初の列の最後のボックスにある必要があります これは少しトリッキーですが、私のやり方は次のとおりです。つまり、最初の列では、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 のソリューション

于 2013-04-01T07:53:02.247 に答える
1

プログラムを使用しない場合、1) に対する答えは 2 であると思います。

最初の行は 1 で始まり、6 で終わります。したがって、行 1 に入る数字は、1 < x < 6 という条件を満たす必要があります。 2 3 4 5. これは、行 1 が 1 2 3 4 5 6 でなければならないことを意味します。

最初の列は 1 で始まり、11 で終わります。最初の列に入れることができる数字は、同様の条件を満たす必要があります: 1 < y < 11. 割り当てられていない残りの数字のうち、この条件を満たすのは 4 つだけです: 7 8 9 10.最初の列は 1 7 8 9 10 11 になります。

残っている数字は 12 13 14 の 3 つだけです。タブローの残りの 3 つのセルにそれらを配置する方法は 2 つしかありません。それらは整理できます：

12 13

14

- また -

12 14

13

コードでこれに取り組もうとすると、強引なルートに行くか、制約の伝播とバックトラッキングの手法を調べることができます。これが、誰かが以前に Prolog を提案した理由です。注目すべきもう 1 つの言語は Python です。

于 2013-03-29T14:58:42.887 に答える
0

これは、制約ロジック プログラミングの問題です。プログラミング言語 Prolog を使用します。clpfd ライブラリを使用した Sicstus プロローグ。

レイアウトを次のように考えます。

ABCDEF
GHI
JK
L
M
N

- コード - 

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
于 2013-03-29T15:49:01.547 に答える