递归与非递归算法求序列所有排列组合

问题描述：

给定已知序列A1A2…An，求出其所有排列组合

一、递归算法

基本思路：

1. 如果n等于1，输出当前序列

2. 否则依次交换Ai(i=1,2..n-1,n)和An

3. 对于前n-1长度序列，重复1、2两步

算法复杂度O（n！）,

算法缺点：如果序列中有重复字符，会出现相同排列组合。递归算法效率低。

算法优点：可以应用于所有字符串序列

二、非递归算法

基本思路：

1. 假设字符都是可比较的，每种排列组合之间都可以比较大小，A1A2…An的最小排列是P1P2…Pn(P1,p2..pn是非严格递增的)。

2. 从P1P2…Pn开始找出刚好比当前排列大的排列。

3. 循环第2步，直到得到最大的排列Pn…P2p1，算法结束。

如何找出刚好比当前排列大的，假设当前排列为B1B2…Bn,

1. 从最右开始，找到第一个递减的字符Bi，Bi<Bi+1，Bi+1>Bi+2>…>Bn，找不到就结束算法

2. 在Bn…Bi+1中找到第一个大于Bi的Bj，交换Bi和Bj，将Bi+1…Bn重新排序成递增排列，新的排列即为所求排列

3. 重复第1步

算法优点：不会出现重复排列组合

算法缺点：只能应用于可比较字符串，或需自定义比较函数

下面给出整数序列的算法代码，主要阐述思想

void Swap(int *a, int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void AscSort(int *array, int n){
    int i, j;
    for(i=n-1; i>=0; i--)
        for(j=0; j<i; j++)
            if(array[j]>array[j+1]) swap(&array[j], &array[j+1]);
}

void ArrayPrintf(int *array, int length){
    int i;
    for(i=0; i<length; i++)
        printf("%d ",array[i]);
    printf("
");
}

void NonRecurLoopArray(int *array, int length){
    AscSort(array, length);
    ArrayPrintf(array,length);
    if(length<=1) return;
    while(true){
        int i = length-1;
        int j = length-1;
        while(i>0 && array[i-1]>=array[i]) --i;
        if(i <= 0) return;
        while(j>i-1 && array[j]<=array[i-1]) j--;
        swap(&array[i-1], &array[j]);
        AscSort(&array[i], length-i);
        ArrayPrintf(array,length);
    }
}

void RecurLoopArray(int *array, int length, int num){
    if(length==1){
        ArrayPrintf(array, num);
        return;
    }
    for(int i=0; i<length; ++i){
        swap(&array[i], &array[length-1]);
        RecurLoopArray(array, length-1, num);
        swap(&array[i], &array[length-1]);
    }
}

递归与非递归算法求序列所有排列组合

相关推荐