输出数组的全排列

思想：

• n 个元素数组全排列 = 第 1 个前缀 + 后 n - 1 个元素全排列
• 输出第 k 个元素之后的全排列：
  • 首先输出以 k 为前缀， 后 n - k 个元素的全排列
  • 然后依次将第 k 个元素与其后的元素互换，再进行后 n - k 个元素的全排列
  • 每一次互换 -> 排列之后，要互换恢复数组，以便于 k 与其后其他元素互换
• 用递归实现，递归到最后一个数时候输出整个数组

#include <iostream>
using namespace std;

void perm(int list[], int k, int m)
{
    if (k == m) //递归到最后一个数，输出list
    {
        for (int i = 0; i < m; i++) {
            cout<<list[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for (int i = k; i < m; i++) //第一次自己和自己换
    {
        swap(list[k], list[i]);
        perm(list, k + 1, m);
        swap(list[k], list[i]); //还原数组
    }
}

int main()
{
    int list[] = {1,2,3,4,5,6} ;
    perm(list, 0, sizeof(list) / sizeof(int));
    return 0;
}