有哪些向量化写法让你拍案叫绝？ 第1页

这题可以答上好一阵子了。。。

1 Permutation问题

问题描述：如果给你1,2,3,...,9，让你写一个函数返回他们的9!=362880个全排列你会怎么做？

我当时在使用R语言开发一个包， 因为很多函数都需要生成全排列，而我又没在网上找到一个合适的代码，就只好自己写了。不小心写了一个R里面最快的出来。我相信肯定有人会优化的比我好，但是目前开源的R代码中我还没有找到，可能这个问题太小众了， 如果有，请告诉我，多谢。

实现相同功能的函数， 我找到了如下几个：

combinat包的permn函数， gtools包的permutations函数，permute包的allPerms函数。 我的代码如下：

鉴于permue包的allPerms函数只能排列7个元素， 我们就对比下从1到7产生全排列的速度好了。 结果如下

速度上直接把他们爆出翔了有木有？ 如果你把7增大的9甚至10。 另外三个函数运算等待的时间会让你酸爽无比。

我来解释下这段代码

这个问题最直观的想法就是用递归， 你去Google搜索算法，十有八九都是用递归的。在generate n个数的全排列的时候，我们会调用generate n-1个数的全排列，如此往复。递归的方法虽然直观，但是当然是最慢的。如果我没记错的话，combinat包的permn函数和gtools的permutations函数都是用了递归的方法，不过刚才我查看了下源代码似乎作者已经优化了。

下面就有人给出来一个递归实现的例子（python）

如果我们把递归变成iterative的情况， 自然就优化了很多。

下面这个网站用了很多种语言来实现， 喜欢写JAVA和C++的可以自行对比比递归方法能快多少。

我在R语言里写循环来避开递归， 但是发现速度比递归还要慢！

其实早在5年前的一次作业里， 我就用了一次向量化的方法来生成全排列， 想法如下：

假设我已经有了2个数的全排列矩阵：

[1， 2;

2， 1]

当我要生产3个数的全排列时，直接新建一个之全部为3的向量，并把他“夹在”两个A之间，就变成了这样：

[ 1, 2, 3, 1, 2;

2, 1, 3, 2, 1]

然后我对这个矩阵“切三刀”， 分别他的(1, 2, 3)列， （2， 3， 4）列， （3， 4， 5）列三个子矩阵：

[1, 2, 3;

2, 1, 3]

[2, 3, 1;

1, 3, 2]

[3, 1, 2;

3 , 2, 1]

OK了， 三个子矩阵纵向排在一起就是3元素的全排列了。 这个程序不难实现， 而且基本都是在矩阵的拼接和取子矩阵的操作。

但是假如我们有更高的要求，我希望返回的全排列是 lexicographical的， 也就是说是按照从大到小的顺序排列的， 那么个这个算法就需要做点修改了。

（注：按照顺序的意思是要按照（1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)这个顺序来排列）

于是乎我又有了新的想法。还是刚才的例子，假如我们已经生成了两个元素的全排列， 我们要生成3个元素的全排列并且是按照顺序来排列的。

要知道，这里的1， 2并不仅仅是元素1， 2， 更重要的是他表示的是下标。 比如我要对两个元素 v = c("tom", "mary")来实现全排列，那么矩阵是应该是这个样子的

[v[1]， v[2];

v[2]， v[1]]

也就是

["tom","mary";

"mary", "tom"]

有了这个认识， 那么就OK了。

我们可以按照这个矩阵分别排列（2， 3） （1， 3） （1， 2）等二元组的全排列（注意我的代码里的series[-p]就是在生成这个二元组）

于是你的矩阵变成了这个样子：

[2， 3;

3， 2]

[1， 3;

3， 1]

[1， 2;

2， 1]

我们只需要在他们的前面分别补充上缺失的第三个元素，1,1,2,2,3,3即可。

（代码的ans[1:faci, 1] = rep(1:i, each = faci_1)就是在补充第一列）

[1， 2， 3;

1， 3， 2]

[2， 1， 3;

2， 3， 1]

[3， 1， 2;

3， 2， 1]

大功告成！

2 repmat问题

这个算法不是我原创，但是绝逼是能用上的最魔性的向量化算法。众所周知Matlab里面有个repmat函数，相比R里面的rep函数，repmat可以直接将矩阵复制M*N次

函数如下：

运行结果

一行代码就搞定了repmat，还是让我惊叹线性代数的美妙！

P.S. 看到自己的包里存在这么一行comments，发现没被打也真是说明没人用这个包啊。。。

其实这段更魔性。。。但是没啥用就不长篇大论了。