年轻人的编程

Question

一个奇怪的问题是:
我在学校解决竞争问题,他们允许我们使用电脑.由于我是竞赛中唯一知道如何编码的人,我使用C和Pascal程序来更快地解决问题.我已经完成了伪代码到代码练习,算法,Collat​​z猜想验证等.
现在,昨天我正在接受下一次挑战训练(4月18日),我看到了一场关于Young tableaux的练习.它的措辞是这样的(我将尽力从意大利语翻译):
"Ferrers图表是N个盒子的配置,分布在一个或多个水平行中,左对齐并配置为每行包含相等或更低的数量这些配置也可以用方框的编号列表来描述,如下图所示:
ferrers diagram http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_m_07a_400.jpg
一个年轻的画面是一个Ferrers N个框的图表填充了从1到N的整数.示例:
young tableaux http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_s_03b_400.jpg
如果框中的数字被排序,以便它们按行和逐列递增,表格是"标准"(例如:第一,第三和第五画面).在标准表格中,第一行的第一个框始终包含1.N始终位于图表的其中一行的最左侧框中.


问题

考虑一个[6,3,2,1,1,1] Ferrers图:
1)如果第一行的第6个框中固定了6,第一列的最后一个框中固定了11,那么有多少种方法可以您是否以标准方式完成图表？

2)如果在第1行的第6个框中固定了7,在第1列的最后一个框中固定了11,那么您可以用多少种方式以标准方式完成图表？

3)如果在第1行的第6个框中固定了8,在第1列的最后一个框中固定了11,那么您可以用多少种方式以标准方式完成图表？"

我试图编写解决方案用矩阵填充这些数字并用"-1"作为"行尾字符",但我卡住了.我怎么能编码"以各种可能的方式填写它以使画面成为标准？".

Answer 1

以下是使用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.

Answer 2

如果不使用程序，我相信 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。