※ 引述《gecer (gecer)》之铭言：
: 标题: Re: [讨论] 排列组合的算法解题
: 时间: Sun Aug 1 21:45:46 2021
:
: 题目如下
: https://ibb.co/kSGwmyk
: 用左边的6个正方形(1~6)pattern将右边的grid(20x10)填满 每一次填入至少含一个
: pattern的正方形(如N.4,只填5) grid不可重复填 要画出所有排列组合并求最小填入
: 次数 初步考虑每个grid有可能被pattern的(1~6)正方形填入 估计大约<6^200种组合
:
看到这个问题觉得有趣想了一下，我的想法如下：
首先复述一下问题：
a. 物件一：带有6种pattern的矩形，数字1~6代表6种pattern，0代表空白
102
000
304
000
506
b. 物件二：20x10的table，最左上角为(0, 0)
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
c. 使用物件一的矩形填满物件二的table
d. 物件一可超过物件二边界，但必须至少一个pattern在边界内
e. 放置物件一矩形时，不可覆蓋到其他pattern，即填入1~6时，只能在0的位置填入
再来是分析填入方法：
i. 由左填至右，由上填至下，每次选择一个pattern填入该格，将整个物件一矩形填入。
如果该格已填，则跳过填下一格。
ii. 是否重复？
对于中间任意格子(x, y)
填入2 = (x-2, y)填入1
填入3 = (x, y-2)填入1
填入4 = (x-2, y-2)填入1
填入5 = (x, y-4)填入1
填入6 = (x-2, y-4)填入1
因此，中间任意格子只需要考虑填入1；
又根据问题c.项，必须填满整个table，因此如果该格是空白，一定是填1
开头部分需特殊处理，参考v.
iii. 是否会覆蓋到已填入pattern？
根据i.和i.i.所述填法，当(x, y)为0，填入1后，会影响的位置为
(x+2, y), (x, y+2), (x+2, y+2), (x, y+4), (x+2, y+4)
当(x+2, y-2)填入1时，(x+2, y)为3，(x+2, y+2)为5，因此可能出现冲突。
一旦出现冲突，代表无法填入1，即(x, y)无填入任何值，违反问题c.项
=> 尝试其他组合
iv. 是否会多算？
否，每格可能为1~6，其pattern分别是：1来自该格，2~6来自前面已填入的格子。
v. 是否会少算？
开头直接填1会少算到填入2~6的可能。
以(0, 0)为例：
如果要填入2，则必须在(-2, 0)填入1
如果要填入3，则必须在(0, -2)填入1
...
所以从(-2, -4)开始填，可填1或不填，意即(0, 0)为6或其他。
当traverse到(0, 0)时，1~6所有可能都跑过，其他格同理。
结论；
一、在物件二开头之前加入特殊区域，从(-2, -4)开始填表，如下图所示：
**********************
**********************
**********************
**********************
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
**00000000000000000000
二、由左至右，由上至下填表，'*'区域可填1或者不填，'0'区域必填1
三、如遇到已填pattern的格子，跳过该格
四、如遇到冲突，返回尝试其他组合
五、统计所有排列组合和填表次数
运用上面一到五，应该就可以找到所有排列组合，至多'*'数平方 (填或不填)
∴ total <= 2^108
另外补上个recursive的pseudo code
long fill_all(x, y, cnt) {
if (x >= TABLE_WIDTH || y >= TABLE_HEIGHT) {
print_table();
min_cnt = MIN(min_cnt, cnt);
return 1;
}
if ((x, y) is in star area) {
n1 = fill_all(next_x, next_y, cnt)
if (try_fill(x, y)) {
n2 = fill_all(next_x, next_y, cnt+1);
clear(x, y);
return n1 + n2;
} else {
return n1;
}
} else {
if (try_fill(x, y)) {
return fill_all(next_x, next_y, cnt+1);
} else {
return 0;
}
}
}
total = fill_all(-2, -4, 0)
以上是我的idea，如果逻辑上有错误，或者有多算或少算，再麻烦各位大大指正。