17

一个奇怪的问题接踵而至：
我在我的学校做一个解决问题的比赛，他们允许我们使用电脑。因为我是比赛中唯一知道如何编码的人，所以我使用 C 和 Pascal 程序来更快地解决问题。我已经通过伪代码到代码的练习、算法、Collat​​z 猜想验证等来做到这一点。
现在，昨天我正在为下一个挑战（4 月 18 日）进行训练，我看到了一个关于 Young 画面的练习。措辞是这样的（我会尽力从意大利语翻译）：
“费雷尔图是分布在一个或多个水平行中的 N 个框的配置，左对齐并配置为使每一行包含的框数与其上的行相同或更少。这些配置也可以通过以下列表来描述盒子的编号，如下图所示：（来源：olimpiadiproblemsolving.it） Young tableau 是 N 个盒子的 Ferrers 图，其中填充了从 1 到 N 的整数。示例：（来源：olimpiadiproblemsolving.it）
费勒图



年轻的画面


如果框中的数字按行和列按升序排序，则该表是“标准”表（例如：第一、第三和第五表）。在标准表格中，第一行的第一个框始终包含 1。N 始终位于图表其中一行的最左边的框中。


问题

考虑一个 [6,3,2,1,1,1] 费雷尔图：
1）如果 6 固定在第一行的第 6 个盒子上，而 11 固定在第一列的最后一个盒子里，有多少种方法可以您以标准方式完成图表？

2) 如果 7 固定在第 1 行的第 6 个盒子上，而 11 固定在第 1 列的最后一个盒子上，你可以用几种方式以标准方式完成图表？

3）如果8固定在第一行的第6个盒子上，11固定在第一列的最后一个盒子上，你可以用多少种方式以标准方式完成图表？”

我试图编写一个解决方案用一个填充了这些数字的矩阵，并用“-1”作为“行结束字符”，但我被卡住了。我该如何编码“以各种可能的方式填充它，以便画面是标准的？”。

4

5 回答 5

6

这是使用 SWI-Prolog 解决第一个问题的示例解决方案：

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

答案是完成画面有两种方式：

?- 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.
于 2013-03-31T23:45:34.683 回答
4

为了解决这个问题，我会使用约束编程（CP）。Young 画面实际上是我在学习新的 CP 系统时尝试解决的标准问题之一。这是迄今为止的实现列表：http: //hakank.org/common_cp_models/#youngtableaux。

我已经更改了“普通”MiniZinc 模型，并针对您的特定问题添加了一些额外的限制。在此处查看完整模型： http ://www.hakank.org/minizinc/young_tableaux_stack_overflow.mzn

（MiniZinc 水平非常高，很容易解决此类问题。）

关于模型中的表示的简短说明：对于大小为 n（n 的分区）的问题，框表示为一个网格（“x”，大小为 n 乘以 n），其值为 1 到 n+1，其中每一行和列按升序排序；所以 n+1 排在最后，并作为一个空值。然后处理分区结构（“p”）以符合 Young/Ferrer 结构（详见模型）。

这三个问题中的每一个都有两个额外的约束（与问题的标准表述相比）：

  • 一定的数字应该在第一行的第 6 个框中添加的约束是 x[1,6] = 6 % or 7 or 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。在可以进入这个画面的 14 个数字中，只有 4 个满足该条件，并且它们是：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。

现在只剩下 3 个数字：12 13 14。在画面的剩余 3 个单元格中只有两种排列方式。他们可以安排：

12 13

14

- 或者 -

12 14

13

试图在代码中解决这个问题，可以走蛮力路线，或者研究约束传播和回溯技术。这就是为什么有人早些时候建议使用 Prolog 的原因。另一种要研究的语言是 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 回答
0

这是著名的 Cormen 书中的一个练习。我发现这个资源有助于学习这个问题，制作这种结构，提取最小元素，并保持数据结构不变。

于 2019-07-23T09:14:02.977 回答