一个用php写的算法 但是估计只有c++的人 愿意帮忙看了

ws00377531

目的，将任意字符，数字，组合数用数组的形式描述，不要求排序。
举例 combination('a','b','c')
得到的结果应是
array(
   array('a'),
   array('b'),
   array('a','b'),
   array('a','c'),
   array('b','c'),
   array('a','b','c'),
)
我的算法在命令行模式下执行combination(array(1,2,3,4,5,6,7,8,10,11,12,13,14,15,16)) ;
排列三次时间分别是
0.109853982925 seconds
0.109352827072 seconds
0.109138011932 seconds

希望能帮忙优化到0.05s左右

Done by  0.151807069778 seconds
Done by  0.150317907333 seconds
Done by  0.165793180466 seconds
Done by  0.152053117752 seconds
Done by  0.158030033112 seconds
Done by  0.161707878113 seconds
Done by  0.155565977097 seconds
Done by  0.153033971786 seconds
Done by  0.156593084335 seconds
Done by  0.154980182648 seconds


function combination($arr = array(),$tmp=0){
        if(count($arr) ==2){
                $test =  array(array($arr[0]),array($arr[1]),array($arr[0],$arr[1]));
                return $test;
        }
        else{
                if(is_array($arr[0])){
                        $len = count($arr);
                        for($i=0;$i<$len;$i++){
                                $arrtmp = $arr[$i];
                                array_push($arrtmp,$tmp);
                                $arr[] = $arrtmp;
                        }
                        $arr[] = array($tmp);
                        return $arr;
                }
                else{  
                        $tmp = $arr[count($arr)-1];
                        array_pop($arr);
                        $array = combination($arr);
                        return  combination($array,$tmp);
                }
        }
}

yikaikai

用c重写

ws00377531

好久不写c       不见得能写出来了

雨过白鹭洲

看下排列组合的算法吧，我不会

但是觉得从算法上来优化，即使是用php，也能提高一些的

joe2k8

这种比较快：

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.         const int N = 16; // N < 32
   
8.         int a[N];
   
9.         for(int i=0; i<N; ++i)
   
10.                 a[i] = i;
    
11.                
    
12.         for(int i = 1; i < (1<<N); ++i)
    
13.         {
    
14.                 for(int j = 0; j < N; ++j)
    
15.                 {
    
16.                         if((1 << j) &i)
    
17.                         {
    
18.                                 //printf("%d ",a[j]);
    
19.                         }
    
20.                 }
    
21.                 //printf("\n");
    
22.         }
    
23.         return 0;       
    
24. }
    

复制代码

去除输出
time ./a.out
real        0m0.005s
user        0m0.004s
sys        0m0.000s

alexhappy

换个好点的机器