作者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