Re: [討論] 排列組合的演算法解題

看板Programming作者gusion時間2年前 (2021/08/07 21:35)推噓0(0推 0噓 5→)

留言5則, 1人參與討論串6/7 (看更多)

※ 引述《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://www.ptt.cc/bbs/Programming/M.1628343343.A.7FA.html