运用Python递归算法实现风神巴巴托斯名字全排列

我们知道，风神温迪的别名除了叫巴巴托斯以外，如果没记错的话，还有“巴斯巴托”，“巴托巴斯”等称呼（bushi）。今天心血来潮，想把她所有四个字“巴巴托斯”的称呼的排列组合给列举出来，想到最近在学Python，因此萌生了用Python写算法实现这一过程的想法。

在介绍算法之前，我们先了解全排列这个概念。从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。我们小学二年级学过，n个元素全排列个数为n!，拿元素(a, b, c)举例，它的全排列一共有(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)六种情况，具体计算逻辑可以看作下图：

我们看图可知，排列的时候首先固定第一个字母，然后再改变后两个字母的顺序，固定第一个字母一共有三种情况，每种情况又对应两个固定后两个字母的情况，因此一共有3*2=6种情况。

如果将n扩大为4，以(a,b,c,d)举例，可以先固定第一个字母确定大类，(a,*,*,*), (b,*,*,*), (c,*,*,*), (d,*,*,*)，每一类的后三个字母又各自有六种情况，所以一共有4*6=24种情况，也就是4!种。以此类推，当n逐个增大时，我们可以找到一个计算规律，那就是，只要会计算n-1个元素，那就很容易算出n个元素的结果。那如何计算n-1个元素的结果呢？那就不断套娃，计算n-2个元素的情况，直至n=1。这种以少推多的计算思想也叫作递归算法，用计算机可以很方便地实现它。具体python代码如下：

这块代码的具体含义是，定义这个递归算法排序函数。具体实现效果如下图所示：

可以看出，上述排序函数成功地将(a,b,c,d)的24种排列都计算了出来。那么回到正题，如果我们将巴巴托斯的全排列计算出来，会有多少种可能呢？

没错，还是24种可能。不过细心的小伙伴会发现，里面有好多重复项。这是因为“巴巴托斯”有两个巴，但是程序并没有把那两个巴看成一个巴，所以一股脑地输出了24种情况。那么我们要去重，具体操作也很简单，只需下面几行代码就可：

具体去重原理是根据24种情况的旧列表重新构造了一个列表，但是往新列表里面添加元素的时候检查里面是否已经有某元素，如果没有，才会添加。最后结果一共有12种情况，也正好是原先的数量除以“巴巴”的排列数。

最后将这12种结果粘贴出来，巴巴托斯，巴巴斯托，巴托巴斯，巴托斯巴，巴斯巴托，巴斯托巴，托巴巴斯，托巴斯巴，托斯巴巴，斯巴巴托，斯巴托巴，斯托巴巴，方便学习、交流、整活。不说了，去抽温迪卡池去，愿小保底不歪。