排列算法分析以及实现

复制代码

function permute($pos) {
    global $m,$n,$used,$p;
    if ($pos == $n) {
        for ($i = 0; $i < $n; $i++) echo $p[$i] + 1;
        echo '<br />';
        return;
    }
    for ($i = 0; $i < $m; $i++) {
        if ($used[$i] == 0) {
            $used[$i] = 1;
            $p[$pos] = $i;
            permute($pos + 1);
            $used[$i] = 0;
        }
    }
} 

$m = 3;
$n = 2;
$used = array();
$p = array();
for ($i = 0; $i < $m;$i++)    $used[$i]=0;
permute(0);


运行如下:

12
13
21
23
31
32

上面的算法是我从网上摘抄下来的,一直没有明白该算法是什么?里面的递归是怎么运作过来的。后来经过几天的思考,现在基本上能够理解。
下面的分析算是我这几天零碎分析的片段整理。

首先为了形象的描述问题,下面我举了个题目。

题目如下:

现在有3数,分别为1、2、3,从中任何2位,组合一个两位数,问总共能组合成多少个两位数,它们分别是多少?

由于便于举例分析,所以上面的数字列出的比较小。

下面是我的一个推导过程。

情况一:先取第一个数1,然后从剩下的两个数中任取一位,那么这时可能的组合情况有12,13;

情况二:先取第二个数2,然后从剩下的两个数中任取一位,那么这时可能的组合情况有21,23;

情况三:先取第三个数3,然后从剩下的两个数中任取一位,那么这时可能的组合情况有31,32;

所以可能组合成6个两位数,它们分别是12,13,21,23,31,32

对于上面的分析,似乎能取出一个结论是:首先从这三个数中任取一位,然后从剩下的数中再任取2-1位。

似乎这就是上面的算法。。

现在将上面的题目数字进一步扩大,然后运用上面的结论来进行分析。

假设现在有4个不同的数,现在要任取3位组合一个新的数。

对于这种情况,当然已经不能再运行第一种方法那么把每一项进行列出来,现在就用上面总结出来的结论进行分析。

情况一,选取第一个数 1,然后从剩下的3个数中取出2个,取法和上面的类似,取出的所有组合和这个数进行组合。

情况二,先取第二个数 2,然后还是从剩下的3个数中取出2个,这里就又回到了上面的例子了,然后还是将所出的组合和这个数进行组合。

……

情况四,先取最后一个数4,然后从剩下的3个数中取出2个,运用上面的例子取法,最后将所有组合和该数进行组合。

这时如果把数字假设成从5个数中任取4个数,是不是,当取完第一个数后,剩下的情况又和上面的一样了,一直到和第一题类似。

一直递归分析,直到分析到从一个数中取一个数为止,然后再次回到上一个数的选择点,又取下一个数,进行同样的分析。直接所有的数都被用完。这个问题似乎和当时的汉诺塔问题比较类似。

对于Amn,首先会选择第一个数,然后心理会想要是能找出m-1个数中任取n-1个数的取法多好,然后又从m-1中选择第一个数,心理又想,要是能找出m-2个数中任取n-2个数中多好啊,一直这样想下去,直到要是能找出2个数中任取一个数的所有取法多好,如果到了这一步,似乎不需要幻想了,因为这一步已经快成为现实了,直接找出最后从一个数中取一个数。然后现依次返回上一层的下一个数,直到这m个数全部选择完为止。

就是这上面算法的原理,这样一步一步的幻想,直接后面幻想成真,就是该算法递归成立的条件。

机器人 2008-10-16 23:20 于 北京

此条目发表在 乱七八糟 分类目录,贴了 标签。将固定链接加入收藏夹。

排列算法分析以及实现》有 4 条评论

  1. 小黑米 说:

    很经典的算法…
    其实递归真的能解决很多问题 哈哈~
    支持~

  2. 小黑米 说:

    好帥啊,照片
    日…拿的還是狙?

  3. hi
    o0jdf01zd5l8u2wn
    good luck

  4. Pingback 引用通告: Latest Telugu Hot Short films 2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>