※ 引述《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/m.aspx?n=bbs/Programming/M.1628343343.A.7FA.html