号码球 -- Zoom.Quiet [2004-08-12 16:33:01]
1. [email protected]
本来以为是一个简单的递归，后来作到凌晨才发现满不是这么一回事儿，要复杂得多。到现在我也不知道这个解是不是对的，欢迎大家讨论。
记得上学时作过这道题，当时是用的统计知识，解法要更简单些。
还有一种最可靠的方法——只是过于“暴力”——生成一个全排列列表，然后用筛法剔除不合要求的项，最后只要count一下即可。只是忘了全排列算法了……脸红…… 书到用时方恨少啊！
PS：我用了那么复杂的递归，运算起来却出乎我意料的快，看来以前是低估了Python解释器的工作效率。
1.1. codeball.py
1 # -*- coding: utf-8 -*-
2
3 #号码球问题
4
5 #求排列，这里采用迭代算法而非递归，
6 #是为了得到更好的效率
7 def P(x, y = None):
8 """
9 求排列数P(x, y)，y默认值为x，此时取P(x)，即x!
10 """
11 if x == 0 or y == 0:
12 return 1
13
14 re = x
15 i = x - 1
16 if y == None:
17 l = 1
18 else:
19 l = x - y
20
21 while i > l:
22 re *= i
23 i -= 1
24 return re
25
26 #求组合
27 def C(x, y):
28 """
29 求组合数C(x, y)
30 """
31 if x == y:
32 return 1
33 else:
34 return P(x, y)/P(y)
35
36 #求号码球（Code Ball）问题，CB1使用递归算法：
37 #1、CB1算法只考虑取出所有球的情况
38 # 即每一个罐子都有一个球对应，没有空罐。
39 #2、CB1(0)时，视作有1种解（这种情况下没
40 #有罐子与球对应）；
41 #3、CB1(1)时，没有解（罐子必然与球对应）；
42 #4、CB1(2)时，有一种解（罐子与球要么完全）
43 #对应，要么完全不对应；
44 #5、CB1(n), n>=3可以分解为用所有可能的排列减去
45 #不合要求的组合。包含有m(m <= n)个重复对应的排
46 #列数为C(n, m)*CB1(n - m)。m取遍n到1，
47 #P(n)与C(n, m)*CB1(n - m)之积加和之差，即为所求。
48 #故：
49 #CB1(3) = P(3) - C(3, 3)*CB1(3 - 3) - C(3, 2)*CB1(3 - 2) - C(3, 1)*CB1(3 - 1)
50 #CB1(n) = P(n) - C(n, n)*CB1(n - n) - C(n, n - 1)*CB1(n - n + 1) - ... - C(n, 1)*CB1(n - 1)
51 # = P(n) - C(n, n)*CB1(0) - C(n, n - 1)*CB1(1) - ... - C(n, 1)*CB1(n - 1)
52 #由C(n, n)==1，CB1(0)==CB1(2)==1，CB1(1)==0，CB1(n)可以简化为：
53 #CB1(n)=P(n) - 1 - C(n, n - 2) - C(n, n - 3)*CB1(3) - ... - n*CB1(n-1)
54 def CB1(x):
55 if x == 0 or x == 2:
56 return 1
57 elif x == 1:
58 return 0
59 else:
60 re = P(x) - 1
61 for i in range(2, x):
62 re -= C(x, x-i)*CB1(i)
63 return re
64
65 print "CB1算法解得CB1(10) = ", CB1(10)
2. Zoom.Quiet
坚决使用暴力!
使用"一切从游戏开始 - ChinesePython Wiki"的技巧来优化
2.1. codeBall.py
1 # -*- coding: gbk -*-
2 # file codeBall.py
3 #/*********************************
4 # \class codeBall
5 # \brief [python-chinese] 趣味问题——号码分配试解
6 # \version 2.0 04427 16:22 [email protected] fixed
7 # \version 1.0 04427 [email protected] 原始提出，现在以最笨方式解决
8 # \author Zoom Quiet (zoomq at itcase.com)
9 # \attention Released under GNU Lesser GPL library license
10 #*********************************/
11
12 import sys, os,string
13 import PnC
14
15 class playCodeBall:
16 def __init__(self):
17 self.log=""
18 def __repr__(self):# 类自述定义
19 print("Zoom.Quiet 最笨方式进行正确解答输出\n 可以作为其它解的验证")
20 return self.log
21 def filter(self,seq,order):
22 seqCB = []
23 length = len(order)
24 tag = 0
25 for item in seq:
26 for i in range(length):
27 #if(i == int(item[i-1])):
28 # 0427;16:22 [email protected] fixed
29 if(i == int(item[i]) - 1):
30 #print "bad CodeBall> %s at [%s] = %s"%(item,i,item[i-1])
31 break
32 else:
33 if(i+1==length):
34 tag = 1
35 if(1==tag):
36 seqCB.append(item)
37 #print item
38 tag = 0
39 return seqCB
40
41 if __name__ == '__main__': # 自测试
42 tryPnC = PnC.permutation() # imported by other programs as well
43 if(tryPnC):
44 #建立序列
45 import timer
46 watch= timer.timer()
47 watch.start()
48 order="12345678"
49 seq = list(order)
50 #生成排列
51 p = tryPnC.permute(seq)
52 #玩——过滤出切题的
53 CB = playCodeBall()
54 result = CB.filter(p,order)
55 print(watch.stop())
56 #print result
57 #输出正确的序列到文件
58 import outputLog
59 exp = outputLog.exporter()
60 exp.exportArrayCB(result)
61 exp.writeInFile("CodeBall.log")
62 #print "当罐有 %s 个时,全部 %s 种排列中,合题的为:%s 种!"%(len(order),len(p),len(result))
63 else:
64 print("\"<!--\n 数码球Zq试解模块 实例创建失败退出!-->\"")
2.1.1. 伺候程序
1 # -*- coding: gbk -*-
2 # file PnC.py
3 #/*********************************
4 # \class PnC
5 # \brief permutation and combination 排列组合 输出
6 # \version 1.0 04427 使用"一切从游戏开始 - ChinesePython Wiki"的技巧
7 # \author Zoom Quiet (zoomq at itcase.com)
8 # \attention Released under GNU Lesser GPL library license
9 # \par
10 # \return
11 # \sa
12 #*********************************/
13
14 import sys, os,string
15 import outputLog
16
17 class permutation:
18 def __init__(self):
19 self.log=""
20 self.export=""
21 def __repr__(self):# 类自述定义
22 return self.log
23 def P(self,x, y = None):
24 """
25 Liux的自然 求排列数P(x, y)，y默认值为x，此时取P(x)，即x!
26 """
27 if x == 0 or y == 0:
28 return 1
29 re = x
30 i = x - 1
31 if y == None:
32 l = 1
33 else:
34 l = x - y
35 while i > l:
36 re *= i
37 i -= 1
38 return re
39 def permute_O_n(self,seq,index):
40 seqc = seq[:]
41 seqn = [seqc.pop()]
42 divider = 2
43 while seqc:
44 index, new_index = divmod(index,divider)
45 seqn.insert(new_index, seqc.pop())
46 divider += 1
47 return ''.join(seqn)
48
49 def permute(self,seq):
50 seqn = [seq.pop()]
51 while seq:
52 newseq = []
53 new = seq.pop()
54 #print "seq:",seq,'seqn', seqn ,'new', new
55 for i in range(len(seqn)):
56 item = seqn[i]
57 for j in range(len(item)+1):
58 newseq.append(''.join([item[:j],new,item[j:]]))
59 seqn = newseq
60 #print 'newseq',newseq
61 return seqn
62
63 if __name__ == '__main__': # 自测试
64 PnC = permutation() # imported by other programs as well
65 if(PnC):
66 seq = list("1234")
67 for i in range(30):
68 print PnC.permute_O_n(seq, i)
69 print(PnC.P(4))
70 else:
71 print("\"<!--\n 排列组合 输出模块 实例创建失败退出!-->\"")
1 # -*- coding: gbk -*-
2 # file outputLog.py
3 #/*********************************
4 # \class outputLog
5 # \brief 结果数据输出支持
6 # \version 1.1 04427 数组的数码球输出辅助 exportArrayCB ...
7 # \version 1.0 04427 支持字串，和数组输出！
8 # \author Zoom Quiet (zoomq at itcase.com)
9 # \attention Released under GNU Lesser GPL library license
10 # \par
11 # \return
12 # \sa
13 #*********************************/
14
15 import sys, os,string
16
17 class exporter:
18 def __init__(self):
19 self.log=""
20 def __repr__(self):# 类自述定义
21 return self.log
22 def writeInFile(self,fname):
23 open(fname,"w").write(self.log)
24 print("成功输出数据到文件:%s"%fname)
25
26 def exportArrayCB(self,seq):
27 foo = ""
28 for i in range(len(seq[0])):
29 foo +=str(i+1)
30 self.log += foo
31 self.log +="\n"+"~"*27+"\n"
32 for i in seq:
33 self.log += i+"\n"
34 self.log +="-"*27+"\n"
35 self.log += foo
36 return self.log
37 def exportArray(self,seq):
38 for i in seq:
39 self.log += i+"\n"
40 return self.log
41 def exportTxt(self,txt):
42 self.log += txt
43 return self.log
44
45 if __name__ == '__main__': # 自测试
46 exp = exporter() # imported by other programs as well
47 if(exp):
48 import PnC
49 tryPnC = PnC.permutation()
50 seq = list("1234")
51 p = tryPnC.permute(seq)
52 exp.exportArrayCB(p)
53 exp.writeInFile("exp.log")
54
55 #open("PnC.log","w").write(PnC.export)
56 else:
57 print("\"<!--\n 结果数据输出支持 实例创建失败退出!-->\"")
1 # -*- coding: gbk -*-
2 # file timer.py
3
4 import sys,os,string,time
5
6 class timer:
7 """/**
8 \class timer
9 \brief 通用Python 程序运行计时器
10 \version 1.0 04427 for 数码球游戏
11 \author Zoom.Quiet ( zoomq at itcase.com)
12 \attention Released under GNU Lesser GPL library license
13 \par usage
14 \li 声明 :watch = timer()
15 \li 跑秒 :watch.start()
16 \li 计时 :watch.stop()
17 \note 只要将watch.start();watch.stop() 分别插入到想测试的代码前后就可以了！
18
19 */
20 """
21 def __init__(self):
22 self.log=""
23 def __repr__(self):# 类自述定义
24 print("利用Python 内含time 模块进行代码计时！")
25 return self.log
26
27 def start(self):
28 """/**
29 \class start
30 \brief 主程序体
31 \version 1.0 04427 for 数码球游戏
32 \author Zoom.Quiet ( zoomq at itcase.com)
33 \attention Released under GNU Lesser GPL library license
34
35 */
36 """
37 self.start= time.time()
38 self.log += "\n run at:"+time.strftime(" %Y-%m-%d %X",time.localtime(self.start))
39 return self.log
40
41 def stop(self):
42 self.stop = time.time()
43 self.log += "\n end at:"+time.strftime(" %Y-%m-%d %X",time.localtime(self.stop))
44 self.log += "\n 本次运行共用时 %s秒"% (self.stop-self.start)
45 return self.log
46
47 def stopMul(self):
48 self.stop = ""
49 self.stop = time.time()
50 self.log += "\n end at:"+time.strftime(" %Y-%m-%d %X",time.localtime(self.stop))
51 self.log += "\n 本次运行共用时 %s秒"% (self.stop-self.start)
52 return self.log
53
54 if __name__ == '__main__': # 自测试
55 watch = timer()
56 if(watch):
57 import CBfilter
58 playCB = CBfilter.CBfilter() # imported by other programs as well
59 watch.start()
60 result = playCB.play(4)
61 print(watch.stopMul())
62 print "#"*7
63 print(watch.stopMul())
64 #print result
65 else:
66 print("\"<!--\n timer 实例创建失败退出!-->\"")
3. 性能对比
来点数学的解释.这个问题其实是错排数的计算问题,如果看过卢开澄的《组合数学》,就会发现错排问题是个很有趣的问题,对它的讨论甚至贯穿全书了. 错排数的计算是有数学方法的,正是[email protected] 给出的,因为规模很小,才10所以速度当然很快.同样Zoomq给的暴力解,也不会太慢.
但事实上这个问题远没有结束,[email protected]给的解法中错排数其实是要通过很多次次迭代才能算出来的,当n很大时(比如1M,实际上经常碰到),这个解法速度也会相当慢,关键是P(x,y)的计算量太大.很不幸,据我所知这个数值的精确解目前好像只有[email protected]给的了,另外还有些估算方法.
4. 用归纳法考虑这个问题
假设n个球时，号码不重复的放法有F(n)个，这时又来了一个罐子和一个球在n+1位置，我们利用球n+1和其它球交换来得到新的放法。
- 对于n个球时每个号码不重复的放法，把球n+1放在1~n的位置，换下来的球放在n+1位置，都可以得到一个新的n+1球时号码不重复的放法，一共有n*F(n)种。
- 另外对于n个球时只有一个号码重复的放法，我们可以把球n+1与号码重复的球进行交换得到新的n+1球时号码不重复的新放法。n个球时，1号重复的放法有F(n-1)种；....n号重复的放法有F(n-1)种，共n*F(n-1)种。所以这样得到的n+1球时号码不重复的新放法有n*F(n-1)种。
由上可得：F(n+1) = n*(F(n) + F(n-1))。
1 # F(n + 1) = n(F(n) + F(n - 1))
2
3 def F(n):
4 if n == 1: return 0
5 if n == 2: return 1
6
7 Fn, Fn_1 = 1, 0
8 for i in xrange(2, n):
9 Fn, Fn_1 = i * (Fn + Fn_1), Fn
10 else:
11 return Fn