分别用C和python实现的数组全排列

一个数组的全排列，就是罗列出数组所有的排列可能，比如，1,2,3
有：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
所有的可能是n!
分析发现：
一个N个数的全排列{1,2,3,.....，n}的全排列perm(n)=r1perm(r2,..,rn),r2perm(r1,r3,...,rn),...rnperm(r1,r2,r3,...,r(n-1))
所以我们可以把要排列的开始的位置和N-1的其他的数做一次交换，这样就是做N-1的全排列，这样一直递归下去，就可以完全求出

用C语言实现的代码如下：

#include <stdio.h>

int n=0;

void swap(int *a ,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void perm(int list[] , int begin , int end)
{
    int i;
    if(begin>end)
    {
        for(i = 0 ; i <=end ; i++)
        {
            printf("%d ",list[i]);
        }
        printf("\n");
        n++;
    }
    else
    {
        for(i = begin ; i<=end; i++)
        {
            swap(&list[begin],&list[i]);
            perm(list,begin+1,end);
            swap(&list[begin],&list[i]);
        }
    }
}

int main()
{
    int list[]={1,2,3,4,5};
    perm(list,0,4);
    printf("total:%d\n",n);
    return 0;
}

用Python实现的代码如下：

'''
Created on 2013年7月22日
对一个数组进行全排列输出
@author: lin
'''
COUNT=0


def perm(num_list,begin,end):
    global COUNT
    if begin>=end:
        print("enter")
        for num in num_list:
            print(num),
        COUNT +=1
    else:
        i = begin
        for num in range(begin,end):
            num_list[num],num_list[i]=num_list[i],num_list[num] #两个数进行交换
            perm(num_list,begin+1,end)
            num_list[num],num_list[i]=num_list[i],num_list[num]
num_list=["1","2","3","4","5"]
perm(num_list,0,5)
print("Total: %s" % COUNT)
exit

python的数组交换还是比较好的 不用那么麻烦