※ 引述《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，如果逻辑上有错误，或者有多算或少算，再麻烦各位大大指正。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 119.14.65.100 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Programming/M.1628343343.A.7FA.html