递归与分治法解决排列问题

问题描述

输入n个元素，对这n个元素进行全排列，列举出所有的结果。

问题分析

第一个元素不动，对后面n-1个元素进行全排列，这样的到的就是以第一个元素为首的所有排列结果，然后将第二个元素作为首元素，对后面n-1个元素进行全排列，以此类推……

#include <stdio.h>
int num = 0;
void swap(char &i,char &j){        //&i代表某类型的变量的引用
    char temp = i;
    i = j;
    j = temp;
}
void perm( char list[],int k,int m ){  //k 要取出的那个数     m  数组的最后一位下标
    //产生list[k,m]的所有排列
    if(k==m){        //只剩一个元素
        for(int i=0;i<=m;i++){
            printf( "%c",list[i]);
        }
        printf("\n");
        num++;
    }else{            //还有多个元素，递归产生排列
        for(int i=k;i<=m;i++){
            swap(list[k],list[i]);        //交换k和i位置的值
            perm(list,k+1,m);
            swap(list[k],list[i]);
        }
    }
}
void main(){
    char list[100];
    int len;
    printf("请输入序列的长度:\n");
    scanf("%d", &len);
    printf("请输入一个序列:\n");
    scanf("%s",list);
    printf("该序列的全排列如下:\n");
    perm(list, 0, len-1);
    printf("该序列共有%d种排列\n", num);
}