Python和C++求排列与组合
排列与组合是信息学奥赛必学内容，同时也是高中数学课程。但是如果要下放到初中甚至小学来教，该如何来教呢？
当我屡次遇到这样的题目，它的基础是排列与组合时，我就思考这个问题。希望学生能更容易的理解它的编程方式。即
如何生成所有的排列或者组合。比如从5个数里面选3个数的所有排列或组合。这个程序该如何编写？我这里用放棋子的
方式来进行讲解。 为了更好理解，先需要具体化一下，也就是举一个例子。在本教程中，我们就以在5个数里面选3个数
的所有排列和组合为例。5个数分别就是[0,1,2,3,4]。从这5个数里取3个数的所有排列是：
[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 2, 1] [0, 2, 3] [0, 2, 4] [0, 3, 1] [0, 3, 2] [0, 3, 4] [0, 4, 1] [0,
4, 2] [0, 4, 3] [1, 0, 2] [1, 0, 3] [1, 0, 4] [1, 2, 0] [1, 2, 3] [1, 2, 4] [1, 3, 0] [1, 3, 2] [1, 3, 4]
[1, 4, 0] [1, 4, 2] [1, 4, 3] [2, 0, 1] [2, 0, 3] [2, 0, 4] [2, 1, 0] [2, 1, 3] [2, 1, 4] [2, 3, 0] [2,
3, 1] [2, 3, 4] [2, 4, 0] [2, 4, 1] [2, 4, 3] [3, 0, 1] [3, 0, 2] [3, 0, 4] [3, 1, 0] [3, 1, 2] [3, 1, 4]
[3, 2, 0] [3, 2, 1] [3, 2, 4] [3, 4, 0] [3, 4, 1] [3, 4, 2] [4, 0, 1] [4, 0, 2] [4, 0, 3] [4, 1, 0] [4,
1, 2] [4, 1, 3] [4, 2, 0] [4, 2, 1] [4, 2, 3] [4, 3, 0] [4, 3, 1] [4, 3, 2]。共有P(5,3)=60种排列。
首先，我们要画一个3行5列的棋盘。如下所示：
我们把求所有排列的过程转换成放棋子的过程。规则为每行每列只放一个，所有棋子的列号不能重复，也就是说在同一列只能有一个棋子。比如对于[0, 1, 2]这个排列，放好了棋子，对应的棋局就是下在这个样子：
通常，我们按行优先来放棋子，也就是说先放第一行的棋子，再放第二行的棋子，依次类推。所以我们就定义一个叫place的函数。它的含义是在当前行放一枚棋子，所以它的参数就是行号，我们用row来作变量名。定义好了这个函数后，那么place(0)就是在索引为0的行放一枚棋子的意思了。由于在一行放棋子的话，在本例中最多都有5种选择，所以place函数中最主要的代码是有一个for循环，用于枚举每一列。如果这一列没有摆放过棋子，那么就能放，则在这里放！然后放下一行的棋子。放一行我们只要递归调用place(row+1)即可。如果下一行的都放完了，那么就要尝试当前行的下一个列。如果这一列没有摆放过棋子，则又像上面这样放棋子，依此继续重复。
在上面，如何记录某个列是否有棋子，而且棋子的行列号到底存储在哪里呢？这里就涉及到数据结构的设计了。我们设一个叫used的列表来记录是否某列是否已被占用。由于共有5列所以它的初始化代码是：used = [False for i in range(5)]。used列表中全初始化为False，表示每一列都没有被占用。我们用一个叫chess的列表来存储棋子的行列号。由于只选3个数，所以它的初始化代码是：chess = [None for i in range(3)]。chess列表中3个值都为None，表示列号未定！ 在下面的代码中，我们看到place是一个递归函数。所以必然要有递归结束条件。在本例中，只放三行，也就是放0和1及2行，所以到了row为3的时候必然是已经放完了一种棋局，所以输出chess即可。代码如下所示：
def place(row): # 在第row行放一枚棋子(以0开始)
if row==3:
print(chess,end=' ')
else:
for col in range(5):
# 如果col列已经放了棋子，必然会标记为True
if used[col]==True:continue
used[col] = True # 标记col列已经被占
chess[row] = col # 放棋子在row,col位置
place(row+1) # 放下一行
chess[row]=None # 取消放棋子
used[col]=False # 取消标记
used = [False for i in range(5)]
chess = [None for i in range(3)]
place(0)
以上代码的C++代码如下所示：
#include
#include
using namespace std;
vector used(5,false);
vector chess(3,-1);
void place(int row){
if(row==3)
{
for(int coll:chess)cout << coll << ' ';
cout << endl;
return;
}
for(int col=0;col<5;col++){
if(used[col]==true)continue;
used[col]=true; //记录在col列已放一枚棋子
chess[row]=col; //保存 (row,col)
place(row+1); //在下一行放置棋子
chess[row]=-1; // -1表示在row行没有放棋子
used[col]=false; //取消记录
}
}
int main(){
place(0);
return 0;
}
那么，如何列出从5个里面选3个数的所有组合呢？我们只要稍微把上面的代码修改一下即可。对于排列[0,1,2]和[0,2,1]。它们都同一个组合，所以本质是去除重复。我们只要规定后面的数大于前面，那就去掉了重复。所以只要把上面的代码加一个判定，即如果放当前行棋子是，需要比较是否比上一行的列号大，如果大才会，否则不能放。代码如下所示：
def place(row): # 在第row行放一枚棋子(以0开始)
if row==3:
print(chess,end=' ')
else:
for col in range(5):
# 如果新放的列号比上一行已经放的棋子的列号相等或者小，不行
if row>0 and col<=chess[row-1]:continue
# 如果col列已经放了棋子，必然会标记为True
if used[col]==True:continue
used[col] = True # 标记col列已经被占
chess[row] = col # 放棋子在row,col位置
place(row+1) # 放下一行
chess[row]=None # 取消放棋子
used[col]=False # 取消标记
used = [False for i in range(5)]
chess = [None for i in range(3)]
place(0)
上面代码的C++代码就没必要列出来了，请读者自行“解决”。 本文章亦放在了本人的微信公众号上，文章网址：https://mp.weixin.qq.com/s/pZn_e_uwZLJaWTpupqafIQ
