推 ptthidebear:我想請問一下如果元素個數和數列個數都是變數要怎處理 04/04 14:18
→ 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)
推 ptthidebear:感謝您!!! 我會好好消化一下的!!! 04/04 18:10
→ ptthidebear:我想請問一下,如果只有s=2的話 應該也只要insert即可? 04/04 18:15
→ ptthidebear:那這樣我可以把s=2列為終止條件嗎@@? 04/04 18:16
→ yauhh:s=2是只做一步insert就好. 嗯,這也是遞迴的一個底. 04/04 19:16
→ ptthidebear:是不是處理這類的問題記憶體的loading都會必然的重呀? 04/04 21:05
→ tkcn:用loading形容記憶體? 我假設你是說需要大量記憶體好了:不會 04/04 21:08
→ ptthidebear:假設要排的單位是一個結構 且要排的數列一多呢...@@? 04/04 21:25
→ ptthidebear:因為感覺排出來的可能結果會很多 每種結果都要存 04/04 21:26
→ yauhh:loading看情況吧,如果你要抓所有的排列放在一組資料結構, 04/04 21:51
→ yauhh:當然要用到空間. 如果只是印出來當然會省空間. 04/04 21:51
→ yauhh:聰明一點做個graph減少複製許多重複的數值空間. 04/04 21:53
→ tkcn:我想不到什麼情況非把所有組合留在記憶體裡，能舉例一下嗎? 04/04 22:02
→ ptthidebear:喔喔~我是指運算的過程中@@" 最後印出來前應該都要先 04/04 22:04
→ ptthidebear:放在記憶體內吧~ 我的意思是這樣 04/04 22:05
→ ptthidebear:另外我說的結構是指 每個元素都是結構 @@" 04/04 22:06
→ tkcn:所以反過來說，如果能夠立刻印出來，就可以省下記憶體囉 :p 04/04 22:38
→ ptthidebear:嗯嗯...Orz 我想請教insert()裡面是C的m+1取n的問題嗎 04/04 22:49
→ ptthidebear:我現在是insert()有點卡關了orz...它應該也是遞迴吧? 04/04 23:54
→ tkcn:其實我覺得換個方式比較好寫，準備一個 m+n 的陣列，把 A 所 04/04 23:57
→ tkcn:有組合放進去，空白的補上 B 04/04 23:58
→ ptthidebear:yauhh大大講的insert方法我大致了解 只是不太懂實做 04/05 00:26
→ ptthidebear:它跟tkcn大您說的方法 有差嗎@@? 04/05 00:27
→ tkcn:我說的方法是只管把 A 插入空白陣列 04/05 00:32
→ yauhh:ok,一般語言真是不好寫,如果用Prolog就很普通... 04/05 09:48
→ yauhh:想不到什麼情況要把組合留在記憶體?一般函數語言就是這樣啊 04/05 09:49
→ yauhh:並不是所有的程式只是像練習題那樣印一印就算了 04/05 09:49
→ 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)
推 ptthidebear:Thanks~ 待我好好消化 XD 04/05 16:48