全排列

一、问题描述

有 n 个数或字符，有多少种排列方法。

二、算法分析

采用分治法把大问题分解成很多的子问题。大问题是所有的排列方法，分解得到的小问题就是以 1 开头的排列，以 2 开头的排列，以 a 开头的排列，以 b 开头的排列...把这些问题继续分解，以 12 开头的排列，以 123 开头的排列...将余下的看成大问题，一直分解下去，直到分解成的子问题只有一个数字或字符的时候，不再分解。

因为 1 个数字或字符肯定只有一种排列方式，现在将每个解决了的小问题合并，合并成一个大点的问题，合并之后这个大点的问题也解决了，再将这些大点的问题合并成一个更大的问题，直到最大的问题解决为止。

先固定一个字符，然后将固定的字符与它后面的每一个进行交换，一直递归下去，直到固定的字符后面只有一个字符。

下图中，红色字符是被固定的字符，白色字符的没有被固定的字符。具体做法就是每次将没有固定的第一个字符与其他未固定的字符交换（第 1 个与第 1个交换，第 1 个与第 2 个交换，... 第 1 个与第 n 个交换），直到只剩下一个没有被固定的字符时，输出此时的字符排列，但是输出之后要将字符的位置还原。

全排列可以看做固定前 i 位，对第 i+1 位之后的再进行全排列，比如固定第一位，后面跟着 n-1 位的全排列。那么解决 n-1 位元素的全排列就能解决 n 位元素的全排列了。

三、代码实现

#include <stdio.h>
#include <string.h>

char temp;
void swapChar(char a[], int i, int k)
{
    temp = a[i];
    a[i] = a[k];
    a[k] = temp;
}

void algorithm(char a[], int start, unsigned long count)
{
    // 深度控制。此时只剩一个没有固定的字符，直接输出
    if(start == count - 1) {
        puts(a);   return;
    }
    
    for(int i = start; i < count; i++) {
        
        swapChar(a, i, start);  // 交换
        
        algorithm(a, start + 1, count);
        
        swapChar(a, i, start);  // 复原
    }
}

int main()
{
    char arr[100] = { 'a', 'b', 'c' };  // gets(a);
    
    algorithm(arr, 0, strlen(arr));
    
    return 0;
}