递归--全排列问题

        前置文章：递归算法：www.jianshu.com/p/703069f3ba3f .

        递归问题有两个经典的应用：Fibonacci数列和汉诺塔问题。我已经在之前的文章里面讲过，而除去这两个问题，还有一些问题是能使用普通方式去求解，但是当用递归的方式去解这道问题的时候，会有种被醍醐灌顶的感觉：嗬，原来这道题还能这么做，真机智。汉诺塔问题也是这样的一个问题。

        我要说的就是这样的一个问题：全排列问题。全排列，非常简单的一种问题，一个全排列的问题你拿去到全国任一所高中，给一高三生，让他去解，基本都能给你做出来，甚至不止一种方法：阶乘、全排列公式……当然，这是全排列在数学上的造诣，当全排列来到算法，来到程序界，就没有这么优美了。

        打个比方，我现在手头有四个水果：橙子、苹果、桃、梨。然后我要将这些水果给挨个排排队，我要选出排起来之后样子最好看的一种组合。

排排队的水果

        那现在问题就来了，这些水果一共能有多少种排队的方式。你拿去问高中生，他会告诉你：这不就是排列组合嘛，A44，也就是4×3×2×1=24种排列方式，然后让写下这些排列方式，挨个挨个写，24种，也不多。那我现在水果不是4种了，我有10种水果要排序，然后写下排列的方式，那你慢慢写吧：10*9*8*7*6*5*4*3*2*1=3628800种。那我好的解决方法就是写一个程序，打印，让电脑去做，我别用人了，不然得累死个人。那我就写一个程序给排队了：

            四个水果问题我直接用一般的解决方法给做：我先把苹果放这，然后我拿梨放苹果左面、右面各放一次，在这里我用数组记录这个顺序，然后用一个统计数记录种数。我梨和苹果放到一起，这就两种方式，我接着拿我的桃，我挨个位置放，这不就插空嘛，我这桃放一次有三个位置，然后我给用数组记录，三个水果放一块了，我这六种方式了，然后我就放橙子了，我这放进去，24种方式，然后我先存到数组，再给输出。这种解决思路就是用排列组合的方式解决这问题。我写一套通用的方法，那我就甭管有多少水果了，反正能把答案输出。

            但是，这样解决这个问题有效率吗？我每插入一个水果，我不停的写入数组、移动数据，当我水果太多的时候，可能也就没法解决了，为啥？数据操作太大，电脑宕机了。

            那这问题咋整？考虑递归吧。我要排这四个水果了，我现在感觉四个有点多，那我就排三个，我先把苹果放在第一个位置上，不管它了，然后我去排桃、橙子、梨去了。然后我就发现了，我这三个水果也能精简，我把桃放第一个位置，我就排橙子和梨就行了，等我排完这俩，我再把橙子放到三个水果的第一个，我在排梨和桃，排完我把梨放第一个，然后排桃和橙子。这我把苹果放到第一个位置的剩下的排序就解决了，那我再把桃放四个水果的第一个位置……这不就是递归嘛，我四个水果的问题能成为四个里面的一个水果和其他三个水果的排列问题。这思路就有了，解决方案就出来了。

void parm(int list[],int k,int m) {

//构成一次全排列，将结果输出

        if(k == m){          

                for (int i=0; i<=m ;i++)

                        cout<< list[i]<<" ";

                cout<<endl;

        }

        else

//在数组里面产生元素k～m的全排列,也就是相当于我把四个水果简化到三个水果

                for(int j=k; j<=m; j++){                                  

                        swap( list[k], list[j] );

                        perm( list, k+1, m );

                        swap( list[k], list[j] );

         }

}

        通过递归的方式，我就把我手里四个水果的排列给找出来了，而且做了这么一个程序，那我以后不管有多少水果我都不怕了。

        我这就挑出最好看的一种排列方式，我就要用这种方式拿着我的水果出去了，我干嘛去，我拿水果喂兔子去。