全排列

闲着无聊，随便写个全排列的递归解，c++能比python快个70倍左右，lisp的那个没法测时间。

先是python的

#!/usr/bin/env python

x=0
def perm(seq, seq_a):
    if len(seq)==0:
        #print seq_a
        global x
        x+=1
    else:
        for i in range(len(seq)):
            tmp_seq=list(seq)
            tmp_seq.remove(seq[i])
            seq_a.append(seq[i])
            perm(tmp_seq,seq_a)
            seq_a.remove(seq[i])
perm(list("hello world"),[])
print x
            

c++的

#include <iostream>
using namespace std;
int count=0;
template<typename T>
void perm(T *seq,T* seq_a,int len , int curr){
    if(curr==len){
        count++;
//        for(int i=0;i<curr;i++)
//            cout<<seq_a[i]<<"\t";
//        cout<<endl;
    }
    for(int i=0;i<len;i++){
        if(seq[i]==0){
            continue;
        }else{
            T tmp=seq[i];
            seq[i]=0;
            seq_a[curr]=tmp;
            curr++;
            perm(seq,seq_a,len,curr);
            curr--;
            seq[i]=tmp;
            seq_a[curr]=0;
        }
    }
}

int main (int argc, char const* argv[])
{
    int a[]={1,2,3,4,5,6,7,8,9,10};
    int b[]={0,0,0,0,0,0,0,0,0,0};
    perm<int>(a,b,10,0);
    cout<<"the number is "<<count<<endl;
    return 0;
}

lisp的

(defun permute (sequence)
  (cond ((null sequence)
         '(()))
        (t (apply 'append (mapcar (lambda (elem) 
                                   (mapcar (lambda (permutesub)
                                          (cons elem permutesub)) (permute (remove elem sequence)))) sequence)))))
(permute '(1 2 3))