组合排列遍历算法浅析(一)


　最近一段时间，稍微空闲了些，于是准备把去年面试某公司时遇到的题写出来。
　　　回味那次面试，真是有点尴尬，大学毕业后，一直忙于这样技术、那样技术，此控件、彼控件的，对于基础的东西忘得差不多了。
于是乎，在面试官一道问题下，顿显尴尬。不过这个面试官的面试方法我觉得挺易做图的……
　　　通过了第一轮电面，第二轮笔试，开始了第三轮面试的时候，面试官开始问一些工作经历上的事情。问得差不多的时候，突然来一句，
这里有一道比较简单的算法题，你来解一下喃：
　　　有n个数，打印出取其中m个数的所有组合。
　　　我当时脑中只记得了C(n,m)这么个符号了，于时我开始努力回忆相关知识……然后面试官就坐我对面，看着我。他越看我越紧张……15分钟后，
我当时先给出了一种算法出来，也不知道对不对，完全没有把握，因为相关知识始终没有回忆起来。然后面试官居看了后，也没有说对或错。只是又来一句，
那我们换另外个简单问题：
　　　有n个数，打印出取其中m个数的所有排列。
　　　这次真尴尬了，过了２５分钟了，我还没有给出算法，面试官就一直在那儿看着我。后来无奈下放弃了。
 
　　　回家后，我心里相当不舒服。开始重新推敲相关的公式。首先，我勉强能记着：
           组合公式C(n,m)=n!/((n-m)!m!),
           然后是排列公式A(n,m)=n!/(n-m)!
         这下没有人一直看着我，我的脑袋终于开始灵光了。在算法设计上，我准备采用递归的思路，然后很快想出解决思路：
　　　１）对于组合，首先我想推敲出C(n,m)与C(n-1,m-1)之间的关系。通过举例的方法，我判断出大概有C(n,m)=C(n-1,m-1)+C(n-1,m)的关系。
然后我开始通过数学来验证：C(n-1,m-1)+C(n-1,m)=(n-1)! / ( (n-m)!(m-1)!) + (n-1)! / ((n-m+1)!m!)
 通分过后=m(n-1)! / ( (n-m)!m!)    +   (n-m)(n-1)! / ((n-m)!m!)=n! / ( (n-m)! m!)=C(n,m)＝C(n,m)
            ＯＫ，这样就可以开始编码了。
 
　　　２）对于排列，我也准备推敲出A(n,m)与A(n-1,m-1)的关系。这个推敲很简单。A(n,m)=n*A(n-1,m-1),推导过程我就不写了。
　　　于是，这里也可以编码了。
 
　　　当时只推出了公式，没有实现编码。等这几天空的时候，我就再把代码补上。对于这里的算法，我在想出递归的方法后，就没有继续去想
动态规划的算法了。如果哪位有更高级的算法，不妨拿出来交流下。感激不尽！

补充：综合编程 , 其他综合 ,