基本算法
全排列算法有这么几种:
(A)字典序法
(B)递增进位制数法
(C)递减进位制数法
(D)邻位对换法
废话不多说，直接上代码
C代码
#include <stdio.h>
#define swap(a,b){long temp=*a;*a=*b;*b=temp;}
static int i=0;
void Permutation(char* pStr, char* pBegin)
{
if(!pStr || !pBegin)
return;
if(*pBegin == 0)
{
i++;
//printf("%s
",pStr);
}
else
{
for(char* pCh = pBegin; *pCh != ' '; pCh++)
{
swap(pCh,pBegin); //swap
Permutation(pStr, pBegin + 1);
swap(pCh,pBegin);//restore
}
}
}
.
void main(){
char str[] ={'a','b','c','d','e','f','h','i','j','k','l','m','n',' '};
char *p=str;
Permutation(p, p);
printf("%d",i);
}
编译运行
[root@dev code]# gcc -o cs allsort.c -std=c99 [root@dev code]# time ./cs 1932053504 real 2m14.918s user 2m14.951s sys 0m0.002s
PHP代码
<?php
/* * 排列组合回溯算法：
* 1. 从 $source 尾部开始往前寻找两个相邻元素（$x,$y)，这两个元素的值满足条件（$x < $y），即前一个比后一个元素大；
* 2. 再次从 $source 尾部开始向前查找，找出第一个大于 $x 的元素（$z），交换 $x 和 $z 元素的值；
* 3. 将 $y 及其之后的所有元素逆向排列，所得排列即为 $source 的下一个组合排列形式。
*/
$arr = array(1,2,3,4,5,6);
$rsd = allsort($arr);
function allsort($arr){
sort($arr);
$len = count($arr)-1;
$rs = array();
$rs[] = implode('',$arr);
$x = $len;
while($x > 0){
$y = $x --;
if($arr[$x] < $arr[$y]){
$z = $len;
while($arr[$x] > $arr[$z]){
$z--;
}
list($arr[$x],$arr[$z]) = array($arr[$z],$arr[$x]);
for($i=$len;$i>$y;$i--,$y++){
list($arr[$i],$arr[$y]) = array($arr[$y],$arr[$i]);
}
$x = $len;
$rs[] = implode('',$arr);
}
}
}
在服务器上运行
[root@localhost ~]# ltrace -c php k3.php 0 256 kb256 kb 19.150321960449 % time seconds usecs/call calls function ------ ----------- ----------- --------- -------------------- 29.32 49.854320 49854320 1 __libc_start_main 13.33 22.661048 433 52289 memcpy 12.55 21.333285 480 44379 pthread_getspecific 11.08 18.831467 650 28958 memcmp 7.74 13.162971 424 30989 malloc 7.71 13.101429 420 31128 free 6.00 10.193844 769 13243 pthread_self 5.15 8.764527 1906 4598 __ctype_b_loc 2.60 4.428846 303 14610 memset 1.57 2.672196 1336098 2 mysql_server_end 1.18 2.001771 222419 9 0.52 0.887929 167 5294 strlen 0.36 0.605670 605670 1 SSL_load_error_strings 0.21 0.362475 181237 2 dlopen 0.18 0.303863 168 1804 strrchr 0.11 0.191724 95862 2 mysql_server_init 0.09 0.149435 163 914 strcasecmp 0.07 0.114988 114988 1 OPENSSL_add_all_algorithms_noconf 0.06 0.104254 167 624 realloc 0.05 0.087413 87413 1 OpenSSL_add_all_ciphers 0.02 0.028834 28834 1 SSL_library_init 0.01 0.025241 25241 1 OpenSSL_add_all_digests 0.01 0.015832 184 86 strtol 0.01 0.015439 160 96 pthread_mutex_unlock 0.01 0.015379 163 94 strncasecmp 0.01 0.015220 158 96 pthread_mutex_lock 0.01 0.014174 164 86 atoi 0.00 0.007627 158 48 strchr 0.00 0.007012 159 44 memchr 0.00 0.006125 191 32 _setjmp 0.00 0.004771 159 30 strdup 0.00 0.004349 181 24 __lxstat 0.00 0.003919 3919 1 xmlInitParser 0.00 0.003668 3668 1 xmlCleanupParser 0.00 0.003068 161 19 tolower 0.00 0.002930 225 13 fflush 0.00 0.002105 263 8 __fxstat 0.00 0.002083 160 13 strtok_r 0.00 0.001900 271 7 write 0.00 0.001892 157 12 fileno 0.00 0.001835 203 9 calloc 0.00 0.001694 1694 1 exit 0.00 0.001618 323 5 fopen 0.00 0.001599 159 10 strcmp 0.00 0.001590 159 10 getenv 0.00 0.001561 1561 1 SSL_get_ex_new_index 0.00 0.001534 170 9 pthread_mutex_init 0.00 0.001286 160 8 pthread_mutex_destroy 0.00 0.001190 1190 1 SYS_exit_group 0.00 0.001169 194 6 floor 0.00 0.001088 362 3 __isinf 0.00 0.001056 211 5 ftell 0.00 0.001050 350 3 open 0.00 0.000920 153 6 __errno_location 0.00 0.000704 704 1 dlclose 0.00 0.000684 171 4 sprintf 0.00 0.000670 167 4 log 0.00 0.000668 222 3 fclose 0.00 0.000633 633 1 tzset 0.00 0.000596 198 3 __isnan 0.00 0.000595 595 1 curl_global_init 0.00 0.000568 568 1 setlocale 0.00 0.000567 189 3 read 0.00 0.000564 188 3 dlsym 0.00 0.000555 277 2 xmlOutputBufferCreateFilenameDefault 0.00 0.000542 180 3 close 0.00 0.000475 158 3 localeconv 0.00 0.000470 235 2 munmap 0.00 0.000467 155 3 strncmp 0.00 0.000409 204 2 signal 0.00 0.000388 194 2 __finite 0.00 0.000378 189 2 isatty 0.00 0.000373 186 2 mmap 0.00 0.000371 185 2 mysql_thread_end 0.00 0.000361 180 2 time 0.00 0.000349 174 2 xmlSetGenericErrorFunc 0.00 0.000335 167 2 xmlSetExternalEntityLoader 0.00 0.000335 167 2 xmlParserInputBufferCreateFilenameDefault 0.00 0.000334 167 2 pow 0.00 0.000321 160 2 mysql_thread_init 0.00 0.000304 152 2 sysconf 0.00 0.000301 150 2 pthread_setspecific 0.00 0.000272 272 1 fgetc 0.00 0.000237 237 1 curl_global_cleanup 0.00 0.000213 213 1 scandir 0.00 0.000201 201 1 __xstat 0.00 0.000198 198 1 getcwd 0.00 0.000194 194 1 readlink 0.00 0.000193 193 1 EVP_cleanup 0.00 0.000190 190 1 gettimeofday 0.00 0.000188 188 1 sigprocmask 0.00 0.000187 187 1 access 0.00 0.000187 187 1 rewind 0.00 0.000182 182 1 xmlRelaxNGCleanupTypes 0.00 0.000179 179 1 xmlSetStructuredErrorFunc 0.00 0.000176 176 1 X509_get_default_cert_area 0.00 0.000175 175 1 pthread_key_delete 0.00 0.000172 172 1 strncat 0.00 0.000170 170 1 snprintf 0.00 0.000170 170 1 pthread_key_create 0.00 0.000168 168 1 __xmlParserVersion 0.00 0.000168 168 1 gnu_get_libc_version 0.00 0.000167 167 1 atol 0.00 0.000159 159 1 strstr 0.00 0.000158 158 1 xmlGetExternalEntityLoader 0.00 0.000156 156 1 sigemptyset 0.00 0.000156 156 1 xmlResetLastError 0.00 0.000153 153 1 sigaddset ------ ----------- ----------- --------- -------------------- 100.00 170.032299 229727 total
可以看到大多数的时间花费在memcpy memcmp 等函数上，CPU密集型的计算还是交给C语言吧