Re: [討論] 排列組合的演算法解題
※ 引述《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
→
08/09 16:20,
3年前
, 1F
08/09 16:20, 1F
→
08/09 16:22,
3年前
, 2F
08/09 16:22, 2F
→
08/09 16:31,
3年前
, 3F
08/09 16:31, 3F
→
08/09 16:34,
3年前
, 4F
08/09 16:34, 4F
→
08/09 16:34,
3年前
, 5F
08/09 16:34, 5F
討論串 (同標題文章)