0002算法笔记——递归排列与Hanoi问题

递归的定义想必大家已经有所了解，此处不再赘述相关概念。接下来将介绍与递归相关的几个典型问题。

1、排列问题

假设R={r1,r2,...,rn}是需要进行排列操作的n个元素组成的集合，Ri=R-{ri}表示从R中移除元素ri后得到的新集合。对于集合X中的元素，其所有可能的排列方式可表示为Perm(X)。而在每个排列前添加前缀ri所形成的排列形式可记作(ri)Perm(X)。基于此，集合R的所有排列可以归纳如下：

当n=1时，Perm(R)的结果仅包含一个元素r，即集合中唯一的成员；

当n>1时，Perm(R)由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)，……,(rn)Perm(Rn)共同组成。

程序代码：

 //2-4 排列问题

    
 #include "stdafx.h"
    
 #include <iostream>     
    
 using namespace std; 
    
  
    
 template <class Type>
    
 inline void Swap(Type &a,Type &b);
    
  
    
 template <class Type>
    
 void Perm(Type list[],int k,int m);