An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20040427/7b4a7a50/attachment.html

伙计，还是在下，没有读您的代码，不好意思，工作太忙了……
不过您一说也就明白了。刚想到了一个递推公式，请斧正:
设在X个球X个罐，一球一罐，罐球不同号的情况下有F(X)种放法，那么
恰有1个球在同号罐中共有 F(X-1)*X 种放法
恰有2个球在同号罐中共有 F(X-2)*C(X,2) 种放法
恰有3个球在同号罐中共有 F(X-3)*C(X,3) 种放法
……
恰有N个球在同号罐中共有 F(X-N)*C(X,N) 种放法
……
X个球都在同号位置上共有 1 种放法

所有这些放法加在一起应该是 X 的阶乘，公式写成：
X!=F(X) + F(X-1)*C(X,1) + F(X-2)*C(X,2) +
F(X-3)*C(X,3) + ...+ F(X-N)*C(X,N) + ...+
F(2)*C(X,X-2) + 1
其中 C(X,N) 是组合公式，算法为 X!/(X-N)!/N!
递推如下：
因为我们已经知道 F(2)=1
那么
3!=F(3) + F(2)*C(3,1) +1
其中 C(3,1) 是唯一的未知数，可以求出。

同理可以递推出 F(4) F(5) …… F(10)……
根据这个递推可以直接编成递归程序，也不需要GOTO
如果您的程序恰好也是这样递归的，就大可不必怀疑其正确性了。

 --- liux at gdcn.com 的正文：
---------------------------------


----- 原邮件 -----

从: "CHEN Guang (Oliver)"
<oliver_guang_chen at yahoo.com.cn>

日期: 星期一, 四月 26日, 2004 下午11:04

主题: Re: 回复:Re:
[python-chinese]趣味问题――号码分配




> 伙计，你提问时不是说用了复杂的递归的吗？ 
> 用SQL语言拼联接查询就不用劳您大驾亲自递归了吧？ 
> 下次记得说话要前后一致才好哟…… 
> 

伙计，你再一次回贴不看贴噢:-目

第一，请回去看看我的源码，是不是用的递归，我的递归是怎么构造的：）

第二，请再回去看看我的mail，所谓的“生成全排列列表，再用筛法过滤”是在什么场合说的:D

偶说话有否前后不一致？

从始至终，感觉您就没仔细看过题目和题解，挑毛病都没挑到点子上，您不是我的仇家派来玩儿我的吧^_^

估计五一也回不去家了，抽空写几个全排列算法什么的，想想也挺有乐趣，嘿嘿……

大家还有什么娱乐节目？刚刚Zoom提到了24点……这个东东很有意思噢，不过我没啥研究，先学习一下大家的经验吧。
> 
> --- liux at gdcn.com 的正文： 
> --------------------------------- 
> 
> 
> ----- 原邮件 ----- 
> 
> 从: "CHEN Guang (Oliver)" 
> <oliver_guang_chen at yahoo.com.cn> 
> 
> 日期: 星期一, 四月 26日, 2004 下午9:53 
> 
> 主题: Re: [python-chinese] 趣味问题――号码分配 
> 
> 
> 
> 
> > 如果仅仅问有多少种算法，那就是10的阶乘了。 
> > 
> > 
>
您的问题是此类问题的一个特例，更普遍的问法是“有X个罐子分别编号1、2、3、4……、X；Y（Y>=X）个球分别编号1、2、3、4……、Y，任意取出X个球以一罐一球的方式放入罐中，问有多少种放法？”这就是PXY（X为上标，Y为下标）的定义了，当X和Y都等于10时就是您的问题了，结果就是P

> 
> > 10 10（一个上标，一个下标）也就是10的阶乘。 
> 
>
下次记得回贴要看贴噢～呵呵，我问的是罐与球完全没有对应的排列有多少种～:-目

> > 
> > 
>
如果要理解一下，可以固定Y=4，然后考查X=1时有多少种放法，X=2时有多少种放法……

> 
> > 
> > 
>
可是如果要让计算机将每种可能的情况都尝试一遍，或者都打印出来，控制流就非常复杂了。

> 
> > 
> > 
>
我曾在七年前编制穷举法解幻方（纵横图）程序时考虑过这个问题，结论是：单纯递归无能为力，GOTO语句必不可少。好在当时使用的

> 
> > Turbo C 
> > 
>
提供了这个语句，才得以解决。可惜那个程序现在找不到了，不过您若感兴趣，我可以回忆一下，写一小段给您。当然用C语言写了，Python不提供GOTO有什么办法……

> 
> > 
> 
>
随便找本大学的组合数学教材就应该有全排列算法，都是很成熟的算法了，比较实用的最少也有三四种。

> 
>
再重复一次，用SQL语言拼联接查询，就可以有迪卡尔积，这是最简单最偷懒的全排列程序。

> > 
> > --- liux at gdcn.com 的正文： 
> > --------------------------------- 
> > 
> > 现有十个分别标有1-10号码的球，十个分别标有1- 
> > 
>
10号码的罐子。每个球放进一个罐子里，现要求每一个球都不能放在同一号码的罐子中，请问有多少种放法？

> 
> > 
>
附件中是我的一种解法，本来以为是一个简单的递归，后来作到凌晨才发现满不是这么一回事儿，要复杂得多。到现在我也不知道这个解是不是对的，欢迎大家讨论。

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

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

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

> 
> 
> > _______________________________________________ 
> > python-chinese list 
> > python-chinese at lists.python.cn 
> > http://python.cn/mailman/listinfo/python-chinese 
> > 
> 
>
_________________________________________________________

> Do You Yahoo!? 
> 惠普TT游戏剧，玩游戏，中大奖！ 
>
http://cn.rd.yahoo.com/mail_cn/tag/SIG=1402c0to2/**http%3A%2F%2Fhp.allyes.com%2Flaserjet%2Fgamestory%2Findex.html%3Fjumpid%3Dex_hphqapcn_MongooseLJ1010%2F201073CN407016%2FYahoo

> _______________________________________________ 
> python-chinese list 
> python-chinese at lists.python.cn 
> http://python.cn/mailman/listinfo/python-chinese 
> 
> _______________________________________________
> python-chinese list
> python-chinese at lists.python.cn
> http://python.cn/mailman/listinfo/python-chinese
>  

_________________________________________________________
Do You Yahoo!? 
惠普TT游戏剧，玩游戏，中大奖！
http://cn.rd.yahoo.com/mail_cn/tag/SIG=1402c0to2/**http%3A%2F%2Fhp.allyes.com%2Flaserjet%2Fgamestory%2Findex.html%3Fjumpid%3Dex_hphqapcn_MongooseLJ1010%2F201073CN407016%2FYahoo