更新时间:2022-09-23 19:13:56
对于全排列,比如有5个字符abcde,则有5!=120种方法.
首先分析出数学递归公式,加上对abcde这个字符串中的字符做全排列。
那么,假设abcde是一个输入参数,输出的值则是一个全排列集合。我们就可以有:
f(abcde)=a+f(bcde) //注意,此处的+号不是简单的加号,而是另一个运算规则,下面会说到。
f(bcde)=b+f(cde)
f(cde)=c+f(de)
f(de)={de,ed}
以上就是运算的递归函数,其中f()函数返回的是一集合,而这里的加号,笔者把它的行为定义为,把一个字符按顺序的插入到一个字符串中。
举个例子:
a+bcde,行为就是把a插在每个位置之间,得到的是如下的一个集合:
abcde,bacde,bcade,bcdae,bcdea
上面是a对单个项进行+操作。
a+f(bcde)则意思是a对一个集合f(bcde)做操作,意味着a对集合中每一个象做+操作。
如上的例子,a对bcde做操作会生成5个项的集合,那么事实上bcde的全排列,根据中学的数学计算推断有4!就是24,f(bcde)有24个项。所以a+f(bcde)意味着a对于这24个项中的每一个项做操作,每个操作生成5个项的,因此总的就会生成5*24=120个项的集合。说到这,你就应该理解+操作的定义了。
事实上,写成+操作只是为了看起来方便,也可以换种表的方式,比如叫做C操作,那么,上述递归的式子也可以写成,
f(abcde)=C(a,f(bcde) )
f(bcde)=C(b,f(cde))
f(cde)=C(c,f(de))
f(de)={de,ed}
这两种表达的数学含义都是一样的。
有了数学意义的表达式,就可以写代码了
c#实现。
本文转自cnn23711151CTO博客,原文链接:http://blog.51cto.com/cnn237111/832060 ,如需转载请自行联系原作者