作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] N數列插隊的問題
時間Sun Apr 4 01:14:16 2010
※ 引述《ptthidebear (= =)》之銘言：
: 其實我也不知道標題打這樣對不對...Orz
: 我的問題如下
: 假設有兩個數列 A = {a1, a2}
: B = {b1, b2}
: 如果我要數列A不動，數列B插入到數列A裡面
: 且插入後B原本的順序不會改變，即：
: 可能的數列為 {b1, b2, a1, a2}
: {b1, a1, b2, a2}
: {b1, a1, a2, b2}
: {a1, b1, b2, a2}
: {a1, b1, a2, b2}
: {a1, a2, b1, b2}
: 以上簡單舉的範例，實際上數列的數目，甚至數列內的元素都可能更多
: 我有點卡關了關於這個問題，
: 不知道板上的大大有沒有辦法幫忙我...Orz
: 順便一問，這個問題算是排列問題還是組合問題呀@@?
看解題方式決定是排列問題或組合問題. 看起來是排列問題,
但若我先看 A 間隙構成的一系列位置為 {1,2,3},
將 B 兩個元素放在 1 2 3 三個位置的其中兩個,並且 B 兩個元素保持順序,
則可以將問題看成是從 {1,2,3} 中取出兩項的組合. 這樣就是組合問題了.
並且是取重覆數字的組合. 重覆數字表示兩個以上的元素插入同一間隙位置.
而處理這個組合問題,程式就是算盤移珠式的處理法了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.228.65
※ 編輯: yauhh 來自: 59.112.228.65 (04/04 01:16)
1F：推 ptthidebear:我想請問一下如果元素個數和數列個數都是變數要怎處理 04/04 14:18
2F：→ ptthidebear:感謝大大願意回我的問題Orz 04/04 14:19
用快一點的講法回答這個問題,先想有一個函數處理插入幾個元素到一個數列:
insert(B[n], A[m])
這是把 n 個 B 項目插入 A 數列, A 數列有 m 個項目. 函數輸出是一大堆組合情況:
insert(B[2], A[2]) ==> { b1, b2, a1, a2 },
{ b1, a1, b2, a2 },
{ a1, b1, b2, a2 },
{ b1, a1, a2, b2 },
{ a1, b1, a2, b2 },
{ a1, a2, b1, b2 }
這個函數做法用 {1,2,3} 取其中兩項並可重覆的組合,依序將 b1 b2 填入兩項位置,
例如,取出的其中一種組合是 {1,3}, 就把 b1 放在 {1} 位置, b2 放在 {3} 位置.
然後把 a1 放在 {1} {2} 位置中間, a2 放在 {2} {3} 位置中間.
哎呀,講得很模糊,看個意思就好.
已知有這個 insert 函數,要把幾個數列合併,就是下列遞迴規則:
combine(L[s]) // L[s] = L1, L2, L3,... , Ls
1. if s = 1, result = L1
2. Else, // s > 1
3. R[k] = insert(L2, L1) // R[k] = R1, R2, R3,... , Rk
4. T3[?] = combine(M3[s-1]) // M3[s-1] = R1, L3, L4,... , Ls
5. T4[?] = combine(M4[s-1]) // M4[s-1] = R2, L3, L4,... , Ls
6. T5[?] = combine(M5[s-1]) // M5[s-1] = R3, L3, L4,... , Ls
... ...
3+k. Tk[?] = combine(Ms[s-1]) // Ms[s-1] = Rk, L3, L4,... , Ls
4+k. result = T[k-2] // T[k-2] = T3[?], T4[?], T5[?],... , Tk[?]
符號系統是我自己定的,慢慢看.
※ 編輯: yauhh 來自: 59.112.230.231 (04/04 17:58)
3F：推 ptthidebear:感謝您!!! 我會好好消化一下的!!! 04/04 18:10
4F：→ ptthidebear:我想請問一下,如果只有s=2的話 應該也只要insert即可? 04/04 18:15
5F：→ ptthidebear:那這樣我可以把s=2列為終止條件嗎@@? 04/04 18:16
6F：→ yauhh:s=2是只做一步insert就好. 嗯,這也是遞迴的一個底. 04/04 19:16
7F：→ ptthidebear:是不是處理這類的問題記憶體的loading都會必然的重呀? 04/04 21:05
8F：→ tkcn:用loading形容記憶體? 我假設你是說需要大量記憶體好了:不會 04/04 21:08
9F：→ ptthidebear:假設要排的單位是一個結構 且要排的數列一多呢...@@? 04/04 21:25
10F：→ ptthidebear:因為感覺排出來的可能結果會很多 每種結果都要存 04/04 21:26
11F：→ yauhh:loading看情況吧,如果你要抓所有的排列放在一組資料結構, 04/04 21:51
12F：→ yauhh:當然要用到空間. 如果只是印出來當然會省空間. 04/04 21:51
13F：→ yauhh:聰明一點做個graph減少複製許多重複的數值空間. 04/04 21:53
14F：→ tkcn:我想不到什麼情況非把所有組合留在記憶體裡，能舉例一下嗎? 04/04 22:02
15F：→ ptthidebear:喔喔~我是指運算的過程中@@" 最後印出來前應該都要先 04/04 22:04
16F：→ ptthidebear:放在記憶體內吧~ 我的意思是這樣 04/04 22:05
17F：→ ptthidebear:另外我說的結構是指 每個元素都是結構 @@" 04/04 22:06
18F：→ tkcn:所以反過來說，如果能夠立刻印出來，就可以省下記憶體囉 :p 04/04 22:38
19F：→ ptthidebear:嗯嗯...Orz 我想請教insert()裡面是C的m+1取n的問題嗎 04/04 22:49
20F：→ ptthidebear:我現在是insert()有點卡關了orz...它應該也是遞迴吧? 04/04 23:54
21F：→ tkcn:其實我覺得換個方式比較好寫，準備一個 m+n 的陣列，把 A 所 04/04 23:57
22F：→ tkcn:有組合放進去，空白的補上 B 04/04 23:58
23F：→ ptthidebear:yauhh大大講的insert方法我大致了解 只是不太懂實做 04/05 00:26
24F：→ ptthidebear:它跟tkcn大您說的方法 有差嗎@@? 04/05 00:27
25F：→ tkcn:我說的方法是只管把 A 插入空白陣列 04/05 00:32
26F：→ yauhh:ok,一般語言真是不好寫,如果用Prolog就很普通... 04/05 09:48
27F：→ yauhh:想不到什麼情況要把組合留在記憶體?一般函數語言就是這樣啊 04/05 09:49
28F：→ yauhh:並不是所有的程式只是像練習題那樣印一印就算了 04/05 09:49
29F：→ yauhh:物件導向語言做起來是把資料留在物件實體中,這也是. 04/05 09:50
insert(B[3],A[2])是先準備k個長度5陣列,k是重覆的C(3,3)扣除後項數字小於前項
的數目,5是A,B項目總數. B三項要填到哪些位置也是要做一下C(3,3),從{1,2,3}取
可重覆的三個數字並扣除後項數字小於前項的情況.
在寫insert函數之前,要先寫C(M,N)的組合與總數,扣掉後項數字小於前項,並檢查
M<N時也得到正確結果.
接下來的問題是把B,A填入長度5陣列,程序是先看B有哪些填入{1}位置,都一個一個填
入長度5陣列,然後把A第一項加在之前填入項的後面,然後看B有哪些填入{2}位置,
一個一個填入,然後把A第二項加在之前填入項的後面,然後把B填入{3}位置的項目填入.
insert函數會由C(3,3)產生k個B填入的組合,例如{1,1,1},{1,1,2},{1,1,3},{1,2,2},
{1,2,3},... 根據k種組合不同的情況,把A[2],B[3]混合複製到k個長度5陣列.
※ 編輯: yauhh 來自: 59.112.230.231 (04/05 10:22)
30F：推 ptthidebear:Thanks~ 待我好好消化 XD 04/05 16:48