当前位置：首页 → 问答吧 → 很笨的方法实现全排列

很笨的方法实现全排列

时间：2006-12-30

来源：互联网

这种方法是我左思右想想出来的，方法很笨，效率很低

有兴趣的看一下

复制PHP内容到剪贴板

PHP代码:

<?php
function full_sort($array){
    $len = count($array);
    for($i=0;$i<$len;$i++){
        $a[]    = 0;
        $numr[] = $i;
    }
    for($a[$len-1]=0;$a[$len-1]<=$len;$a[$len-1]++){
        if($a[0]==$len) break;
        for($i=1;$i<$len;$i++){
            if($a[$i]==$len){
                $a[$i-1]++;
                for($j=$i;$j<$len-1;$j++){
                    $a[$i]=0;
                }
                $a[$len-1]=-1;
                $skip=true;
                break;
            }
        }
        if($skip){
            $skip=false;
            continue;
        }
        $pass =1;
        foreach($numr as $num){
            if(in_array($num,$a)){
                $pass *= 1;
            }else{
                $pass *= 0;
            }
        }
        if($pass){
            $k++;
            for($i=0;$i<$len;$i++){
                $str.= $array[$a[$i]];
            }
            $str.= "<br>";
        }
    }
    $str.=$k;
    return $str;
}
$array = array("a","b","c","d","e","f");
echo full_sort($array);
?>

作者: muqiao 发布时间: 2006-12-30

复制PHP内容到剪贴板

PHP代码:

$array = array("a","b","c","d","e","f","g");
set_time_limit(0);
$begin = explode(' ', microtime());
echo full_sort($array);
$end = explode(' ', microtime());
$time = ($end[0]+$end[1]) - ($begin[0]+$begin[1]);
echo '<br>';
echo "执行时间：{$time}秒";

执行时间：8.63643407822秒

我晕喽！！

作者: muqiao 发布时间: 2006-12-30

$array = array("a","b","c","d","e","f");
执行时间：0.389720201492秒
一个就差这么远啦？

作者: muqiao 发布时间: 2006-12-30

为什么会这么慢撒？
实际上至少循环了10^N N为字符个数

作者: muqiao 发布时间: 2006-12-30

<?
//写个递归版本.
//9个以上会很慢, 内存占用狂增,本机测试:用时48秒左右, php.exe占用内存最高800M左右,注意:内存小者勿试
function fullSort($a,$count)
{
      $result=array();
      if($count==2){
            $result[]=$a;
            $result[]=array($a[1],$a[0]);
            return $result;
      }elseif($count==1){
            return $a;
      }
      for($i=0;$i<$count;$i++){
            $a0 =array_shift($a);
            $ir = fullSort($a,$count-1);
            foreach($ir as $r){
                     array_unshift($r,$a0);
                     $result[] = $r;
            }
            array_push($a,$a0);
      }
      return $result;
}

$a = array('a','b','c','d','e','f','g');
$bt = array_sum(explode(' ',microtime()));
$result = fullSort($a,count($a));
$et = array_sum(explode(' ',microtime()));
echo '用时:', $et-$bt, '秒';

foreach($result as $r)
{
      echo "\n",implode('',$r);
}
?>
用时:0.186951160431秒

[[i] 本帖最后由 litqqs 于 2007-1-3 02:34 编辑 [/i]]

作者: litqqs 发布时间: 2007-01-03

楼上递归的很好
php中的函数我知道的很少
array_shift()
array_unshift()
array_push()
我都不知道干什么的

在我机子上运行你的代码用时:0.231194972992秒

在你机子上试试这个

复制PHP内容到剪贴板

PHP代码:

<?php
function gosort($array,$len){
    if($len<=2){
        $rs_array[0]=$array[0].$array[1];
        $rs_array[1]=$array[1].$array[0];
    }else{
        for($i=0;$i<$len;$i++){
            $leave_one=$array[$i];
            $k=0;
            for($j=0;$j<$len;$j++){
                if($j==$i){
                    continue;
                }else{
                    $tosent[$k]= $array[$j];
                    $k++;
                }
            }
            $fetch = gosort($tosent,$len-1);
            foreach($fetch as $comein){
                $rs_array[] = $leave_one.$comein;
            }
        }
    }
    return $rs_array;
}

//example
$array =array("a","b","c","d","e","f","g");
set_time_limit(0);
$begin = explode(' ', microtime());
$comeonbaby = gosort($array,7);
$f=0;
foreach($comeonbaby as $menu){
    echo $menu."<br>";
    $f++;
}
echo $f;
$end = explode(' ', microtime());
$time = ($end[0]+$end[1]) - ($begin[0]+$begin[1]);
echo '<br>';
echo "执行时间：{$time}秒";
?>

这个执行时间：0.0428099632263秒

我研究这个是想用来计算行列式
我的这个方法虽然已经够快了，还是不行，10个以上字符我电脑CPU 99％被apache占了，好长一段时间都不出结果，

也不知道到底要用多长时间，总之计算不出来了，这种用来开发web的语言不适于用来计算这些东西

作者: muqiao 发布时间: 2007-01-03