## page was renamed from PyPorgramGames/CodeBall
##language:zh
'''
号码球
'''
-- Zoom.Quiet [<<DateTime(2004-08-12T16:33:01Z)>>]
<<TableOfContents>>
= liux@gdcn.com =
本来以为是一个简单的递归，后来作到凌晨才发现满不是这么一回事儿，要复杂得多。到现在我也不知道这个解是不是对的，欢迎大家讨论。

记得上学时作过这道题，当时是用的统计知识，解法要更简单些。

还有一种最可靠的方法——只是过于“暴力”——生成一个全排列列表，然后用筛法剔除不合要求的项，最后只要count一下即可。只是忘了全排列算法了……脸红……
书到用时方恨少啊！

PS：我用了那么复杂的递归，运算起来却出乎我意料的快，看来以前是低估了Python解释器的工作效率。

== codeball.py ==
{{{
#!python
# -*- coding: utf-8 -*-

#号码球问题

#求排列，这里采用迭代算法而非递归，
#是为了得到更好的效率
def P(x, y = None):
	"""
    	求排列数P(x, y)，y默认值为x，此时取P(x)，即x!
	"""
	if x == 0 or y == 0:
		return 1
    
	re = x
	i = x - 1
	if y == None:
		l = 1
	else:
		l = x - y

	while i > l:
		re *= i
		i -= 1
	return re

#求组合
def C(x, y):
	"""
	求组合数C(x, y)
	"""
	if x == y:
		return 1
	else:
		return P(x, y)/P(y)

#求号码球（Code Ball）问题，CB1使用递归算法：
#1、CB1算法只考虑取出所有球的情况
#	即每一个罐子都有一个球对应，没有空罐。
#2、CB1(0)时，视作有1种解（这种情况下没
#有罐子与球对应）；
#3、CB1(1)时，没有解（罐子必然与球对应）；
#4、CB1(2)时，有一种解（罐子与球要么完全）
#对应，要么完全不对应；
#5、CB1(n), n>=3可以分解为用所有可能的排列减去
#不合要求的组合。包含有m(m <= n)个重复对应的排
#列数为C(n, m)*CB1(n - m)。m取遍n到1，
#P(n)与C(n, m)*CB1(n - m)之积加和之差，即为所求。
#故：
#CB1(3) = P(3) - C(3, 3)*CB1(3 - 3) - C(3, 2)*CB1(3 - 2) - C(3, 1)*CB1(3 - 1) 
#CB1(n) = P(n) - C(n, n)*CB1(n - n) - C(n, n - 1)*CB1(n - n + 1) - ... - C(n, 1)*CB1(n - 1)
#		= P(n) - C(n, n)*CB1(0) - C(n, n - 1)*CB1(1) - ... - C(n, 1)*CB1(n - 1)
#由C(n, n)==1，CB1(0)==CB1(2)==1，CB1(1)==0，CB1(n)可以简化为：
#CB1(n)=P(n) - 1 - C(n, n - 2) - C(n, n - 3)*CB1(3) - ... - n*CB1(n-1)
def CB1(x):
	if x == 0 or x == 2:
		return 1
	elif x == 1:
		return 0
	else:
		re = P(x) - 1
		for i in range(2, x):
			re -= C(x, x-i)*CB1(i)
		return re

print "CB1算法解得CB1(10) = ", CB1(10)
}}}

= Zoom.Quiet =
坚决使用暴力!

使用"[[http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_ce_cf_b7_bf_aa_ca_bc|一切从游戏开始]] - ChinesePython Wiki"的技巧来优化

== codeBall.py ==
{{{
#!python
# -*- coding: gbk -*-
# file codeBall.py
#/*********************************
# \class codeBall
# \brief 	[python-chinese] 趣味问题——号码分配试解
# \version 2.0  04427	16:22 liux@gdcn.com fixed
# \version 1.0  04427	liux@gdcn.com 原始提出，现在以最笨方式解决
# \author Zoom Quiet (zoomq at itcase.com)
# \attention 	Released under GNU Lesser GPL library license
#*********************************/

import sys, os,string
import PnC

class playCodeBall:
    def __init__(self):
        self.log=""
    def __repr__(self):# 类自述定义
        print("Zoom.Quiet 最笨方式进行正确解答输出\n 可以作为其它解的验证")
        return self.log
    def filter(self,seq,order):        
        seqCB = []
        length = len(order)
        tag = 0
        for item in seq:            
            for i in range(length):
                #if(i == int(item[i-1])):
                # 0427;16:22 liux@gdcn.com fixed
                if(i == int(item[i]) - 1):
                    #print "bad CodeBall> %s at [%s] = %s"%(item,i,item[i-1])
                    break
                else:                    
                    if(i+1==length):
                        tag = 1                    
            if(1==tag):
                seqCB.append(item)
                #print item
                tag = 0
        return seqCB

if __name__ == '__main__':      # 自测试
    tryPnC = PnC.permutation()            # imported by other programs as well
    if(tryPnC):
        #建立序列
        import timer
        watch= timer.timer()
        watch.start()
        order="12345678"
        seq = list(order)
        #生成排列
        p = tryPnC.permute(seq)        
        #玩——过滤出切题的
        CB = playCodeBall()
        result = CB.filter(p,order)
        print(watch.stop())
        #print result
        #输出正确的序列到文件
        import outputLog
        exp = outputLog.exporter()
        exp.exportArrayCB(result)
        exp.writeInFile("CodeBall.log")
        #print "当罐有 %s 个时,全部 %s 种排列中,合题的为:%s 种!"%(len(order),len(p),len(result))
    else:
        print("\"<!--\n   数码球Zq试解模块 实例创建失败退出!-->\"")
}}}    
    
=== 伺候程序 ===
{{{
#!python
# -*- coding: gbk -*-
# file PnC.py
#/*********************************
# \class PnC
# \brief 	permutation and combination 排列组合 输出
# \version 1.0  04427	使用"一切从游戏开始 - ChinesePython Wiki"的技巧
# \author Zoom Quiet (zoomq at itcase.com)
# \attention 	Released under GNU Lesser GPL library license
# \par
# \return
# \sa
#*********************************/

import sys, os,string
import outputLog

class permutation:
    def __init__(self):
        self.log=""
        self.export=""
    def __repr__(self):# 类自述定义
        return self.log
    def P(self,x, y = None):
    	"""
        	Liux的自然 求排列数P(x, y)，y默认值为x，此时取P(x)，即x!
    	"""
    	if x == 0 or y == 0:
    		return 1        
    	re = x
    	i = x - 1
    	if y == None:
    		l = 1
    	else:
    		l = x - y    
    	while i > l:
    		re *= i
    		i -= 1
    	return re    
    def permute_O_n(self,seq,index):
        seqc = seq[:]
        seqn = [seqc.pop()]
        divider = 2
        while seqc:
            index, new_index = divmod(index,divider)
            seqn.insert(new_index, seqc.pop())
            divider += 1
        return ''.join(seqn)
        
    def permute(self,seq):
        seqn = [seq.pop()]
        while seq:
            newseq = []
            new = seq.pop()
            #print "seq:",seq,'seqn', seqn ,'new', new
            for i in range(len(seqn)):
                item = seqn[i]
                for j in range(len(item)+1):
                    newseq.append(''.join([item[:j],new,item[j:]]))
            seqn = newseq
            #print 'newseq',newseq
        return  seqn

if __name__ == '__main__':      # 自测试
    PnC = permutation()            # imported by other programs as well
    if(PnC):
        seq = list("1234")
        for i in range(30):
            print PnC.permute_O_n(seq, i)
        print(PnC.P(4))
    else:
        print("\"<!--\n   排列组合 输出模块 实例创建失败退出!-->\"")
}}}

-----
{{{
#!python
# -*- coding: gbk -*-
# file outputLog.py
#/*********************************
# \class outputLog
# \brief 	结果数据输出支持
# \version 1.1  04427	数组的数码球输出辅助 exportArrayCB ...
# \version 1.0  04427	支持字串，和数组输出！
# \author Zoom Quiet (zoomq at itcase.com)
# \attention 	Released under GNU Lesser GPL library license
# \par
# \return
# \sa
#*********************************/

import sys, os,string

class exporter:
    def __init__(self):
        self.log=""
    def __repr__(self):# 类自述定义
        return self.log
    def writeInFile(self,fname):
        open(fname,"w").write(self.log)
        print("成功输出数据到文件:%s"%fname)
        
    def exportArrayCB(self,seq):
        foo = ""
        for i in range(len(seq[0])):
            foo +=str(i+1)
        self.log += foo
        self.log +="\n"+"~"*27+"\n"
        for i in seq:
            self.log += i+"\n"
        self.log +="-"*27+"\n"
        self.log += foo
        return self.log
    def exportArray(self,seq):
        for i in seq:
            self.log += i+"\n"
        return self.log
    def exportTxt(self,txt):
        self.log += txt
        return self.log

if __name__ == '__main__':      # 自测试
    exp = exporter()            # imported by other programs as well
    if(exp):
        import PnC
        tryPnC = PnC.permutation()
        seq = list("1234")
        p = tryPnC.permute(seq)
        exp.exportArrayCB(p)
        exp.writeInFile("exp.log")
        
        #open("PnC.log","w").write(PnC.export)
    else:
        print("\"<!--\n   结果数据输出支持 实例创建失败退出!-->\"")
}}}

--------------
{{{
#!python
# -*- coding: gbk -*-
# file timer.py

import sys,os,string,time

class timer:
    """/**
     \class timer
     \brief    通用Python 程序运行计时器
     \version 1.0  04427	for 数码球游戏
     \author Zoom.Quiet ( zoomq at itcase.com)
     \attention 	Released under GNU Lesser GPL library license
     \par usage
       \li 声明 :watch = timer()
       \li 跑秒 :watch.start()
       \li 计时 :watch.stop()
     \note 只要将watch.start();watch.stop() 分别插入到想测试的代码前后就可以了！
    
    */
    """
    def __init__(self):
        self.log=""
    def __repr__(self):# 类自述定义
        print("利用Python 内含time 模块进行代码计时！")
        return self.log
    
    def start(self):
        """/**
         \class start
         \brief    主程序体
         \version 1.0  04427	for 数码球游戏
         \author Zoom.Quiet ( zoomq at itcase.com)
         \attention 	Released under GNU Lesser GPL library license
         
        */
        """
        self.start= time.time()
        self.log += "\n run at:"+time.strftime(" %Y-%m-%d %X",time.localtime(self.start))
        return self.log
    
    def stop(self):
        self.stop = time.time()
        self.log += "\n end at:"+time.strftime(" %Y-%m-%d %X",time.localtime(self.stop))
        self.log += "\n 本次运行共用时 %s秒"% (self.stop-self.start)
        return self.log
    
    def stopMul(self):
        self.stop = ""
        self.stop = time.time()
        self.log += "\n end at:"+time.strftime(" %Y-%m-%d %X",time.localtime(self.stop))
        self.log += "\n 本次运行共用时 %s秒"% (self.stop-self.start)
        return self.log

if __name__ == '__main__':      # 自测试
    watch = timer()        
    if(watch):
        import CBfilter
        playCB = CBfilter.CBfilter()            # imported by other programs as well
        watch.start()
        result = playCB.play(4)
        print(watch.stopMul())
        print "#"*7
        print(watch.stopMul())
        #print result
    else:
        print("\"<!--\n   timer 实例创建失败退出!-->\"")
}}}
   
= 性能对比 =
来点数学的解释.这个问题其实是错排数的计算问题,如果看过卢开澄的《组合数学》,就会发现错排问题是个很有趣的问题,对它的讨论甚至贯穿全书了.
错排数的计算是有数学方法的,正是liux@gdcn.com 给出的,因为规模很小,才10所以速度当然很快.同样Zoomq给的暴力解,也不会太慢.

但事实上这个问题远没有结束,liux@gdcn.com给的解法中错排数其实是要通过很多次次迭代才能算出来的,当n很大时(比如1M,实际上经常碰到),这个解法速度也会相当慢,关键是P(x,y)的计算量太大.很不幸,据我所知这个数值的精确解目前好像只有liux@gdcn.com给的了,另外还有些估算方法.

= 用归纳法考虑这个问题 =
假设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))。
{{{
#!python
# F(n + 1) = n(F(n) + F(n - 1))

def F(n):
    if n == 1: return 0
    if n == 2: return 1

    Fn, Fn_1 = 1, 0
    for i in xrange(2, n):
	Fn, Fn_1 = i * (Fn + Fn_1), Fn
    else:
	return Fn
}}}