号码球 -- 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