[通用技术]在不同语言中用协程实现全排列算法（C++/Lua/Python/C#） ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

我这里实现全排列的基本算法如下（C++）：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <vector>
 4 
 5 void perm(std::vector<int>& v, int pos = 0)
 6 {
 7     if (pos == v.size()) {
 8         for (int i = 0; i < v.size(); ++i) {
 9             std::cout << v[i] << ',';
10         }
11         std::cout << std::endl;
12     }
13     for (int i = pos; i < v.size(); ++i) {
14         std::swap(v[i], v[pos]);
15         perm(v, pos + 1);
16         std::swap(v[i], v[pos]);
17     }
18 }
19 
20 int main()
21 {
22     std::vector<int> v;
23     for (int i = 1; i <= 4; ++i) v.push_back(i);
24     perm(v);
25 }

这是一种最简洁的算法，即，在每轮递归中，依次选择一项数据放在当前参考位置，然后移动参考位置，并进入更深一级递归。
这里的C++实现，简单，但是灵活性不够。上面的例子，对全排列的每个状态，只能够打印输出。当然，为perm函数添加一个函数指针，用不同的函数行为来替代打印操作，可以稍微提高灵活性。但，我这里所说的灵活性受限，主要是指，上面的算法只能一口气处理所有的全排列状态，不能中断这个过程。是的，你也可以为上面的perm函数提供一个容器，收集所有排列状态，待顶层perm函数返回后，再对搜集的结果进行进一步处理，但是，当排列状态过多时，搜集状态的容器会占用很大的内存。能不能把数组的所有排列状态看作一个集合，然后用迭代器去访问这整个集合？迭代器的灵活性能够满足我的需要，最好，迭代过程中，也没有数据堆积，不会出现内存占用太多的情况。

C++的STL中有符合要求的算法：std::next_permutation。

使用如下：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <vector>
 4 
 5 int main()
 6 {
 7     std::vector<int> v;
 8     for (int i = 1; i <= 4; ++i) v.push_back(i);
 9     do {
10         for (int i = 0; i < v.size(); ++i) {
11             std::cout << v[i] << ',';
12         }
13         std::cout << std::endl;
14     } while (std::next_permutation(v.begin(), v.end()));
15 }

next_permutation这个函数，能够满足我的需求。它灵活，快速，并且没有多余的内存占用。不过，我关注的焦点不在它，因为它采用了一种更复杂的算法。具体的算法实现，可以自行查看该函数的源码，另外，侯捷《STL源码剖析》一书中，对该算法的原理有清楚的解释。

我希望的是，算法如第一例般简明易懂，使用起来又有如迭代器般灵活。

为了这个目标，我想到协程。

C/C++的话，Windows下有CreateFiber等一组函数能够创建和切换协程。由于Lua中的协程和Windows的Fiber使用大同小异，这里我就直接转到Lua的协程-coroutine了。

 1  function _perm(arr, pos) 
 2      pos = pos or 1
 3      if pos == #arr then 
 4          coroutine.yield(arr) 
 5      end 
 6      for i = pos, #arr do 
 7          arr[i], arr[pos] = arr[pos], arr[i]
 8          _perm(arr, pos + 1)
 9          arr[i], arr[pos] = arr[pos], arr[i]
10      end
11  end
12 
13  function perm(arr)
14      return coroutine.wrap(function()
15          _perm(arr)
16      end)
17  end
18 
19  for i in perm({1, 2, 3, 4}) do
20      table.foreach(i, function(_, v) io.write(v, ',') end)
21      print()
22  end

可以看到，上面的_perm函数和C++版的perm几乎相同，只是把打印数组的语句换成了coroutine.yield。

_perm实现了算法的主体部分，而perm则是将_perm包装成协程迭代器后返回给外部使用。这个实现，既保持了算法的清晰性，又得到了极高的灵活度。

当然，协程不是没有开销的，协程其实是另外开辟了一个栈的空间，在上面返回的coroutine迭代其销毁前，这份额外的栈内存一直存在。但是，肯定比收集所有状态再逐一访问的方案更优，因为，协程中的栈帧最多不过n层，而前者的内存占用是n!。

之前我还测试过，将STL中的next_permutation算法移植到Lua中，再和协程版本比效率，结果是协程版本输了，但两者的用时也较接近。毕竟协程是一种用空间/时间换清晰性，控制软件复杂度的方案，不应该对它的性能苛求太多。当然，只针对全排列这个问题，采用next_permutation算法是最好了。

本来，说过Lua的协程版全排列算法后，我这篇文章也该结束了，但事实上，由于在不同的语言中，协程的用法不尽相同，一些语言中的协程在使用上会有一些局限，因此，部分语言的协程在解决特定问题时，可能会遇到点麻烦。

我在很长的时间里，都没意识到，C#的yield return其实是协程设施，直到我最近学Python时，看到有人指出，Python的协程就是send和yield，我才恍然大悟。

在需要自动生成迭代器时，yield这货，它表现得极为犀利，也因此，各种语言入门书，但凡讲yield，都用迭代器的生成作为示例。事实上，yield在实现类似Linq to object这样的多级延迟迭代的函数库时，确实能够发挥及其强大的威力。

和Lua/Win-API版本的协程相比，C#/Python中的协程更为高效，因为它的实现并没有借助栈，内存占用更少，但是，也因此，后者的协程在用法上有了一个限制：yield应该放在同一个函数的函数体中，即是说，在Python中，不能在外层函数中yield后，又简单的进入内层函数再yield。这是因为，外层函数对内层函数的调用，并不会执行内层函数函数体的代码，这个调用的结果，只是一个表达式，一个迭代器对象。

这是一段Lua代码：

 1 function bar()
 2     coroutine.yield(2)
 3 end
 4 
 5 function foo()
 6     coroutine.yield(1)
 7     bar()
 8     coroutine.yield(3)
 9 end
10 
11 for i in coroutine.wrap(foo) do
12     print(i)
13 end

它输出的是1，2，3.

这是一段Python代码：

 1 def bar():
 2     yield 2
 3 
 4 def foo():
 5     yield 1
 6     bar()
 7     yield 3
 8 
 9 for i in foo():
10     print i

它输出1，3.

因为二者的协程实现方案是不同的！Python中的bar()调用，只会返回一个迭代器，而不会执行任何bar函数体中的语句！

其实说到这里，结论已经很明显了：在C#/Python中，如果需要跨多个函数帧来yield的话，不能简单的调用含yield的内层函数，而是应该代之以这种语句：

1 for i in foo(): yield i

这里的foo就是含yield的内层函数。不管foo内部的yield语句后面有没有表达式，即，不管上面的i是否为None，都应该在含yield的外层函数中，将foo()调用替换乘上面的语句，这样才能榨干foo，执行foo中应该被执行的每条语句。

在发现C#的yield return就是协程之前，我一度认为yield是不能用于解决全排列这个问题的，直到我认真思考，得出上面这个结论之后。这样看来，yield这种协程方案，功能是和Lua的coroutine等效的了。

这是Python的全排列实现：

 1 def perm(arr, pos = 0):
 2     if pos == len(arr):
 3         yield arr
 4 
 5     for i in range(pos, len(arr)):
 6         arr[pos], arr[i] = arr[i], arr[pos]
 7         for _ in perm(arr, pos + 1): yield _
 8         arr[pos], arr[i] = arr[i], arr[pos]
 9 
10 for i in perm([1,2,3,4]):
11     print i

当然，C#也一样：

 1 static void Swap<T>(ref T a, ref T b)
 2 {
 3     T t = a;
 4     a = b;
 5     b = t;
 6 }
 7 
 8 static IEnumerable<int[]> Perm(int[] arr, int pos)
 9 {
10     if (pos == arr.Length)
11     {
12         yield return arr;
13     }
14     for (int i = pos; i < arr.Length; ++i)
15     {
16         Swap(ref arr[i], ref arr[pos]);
17         foreach (var j in Perm(arr, pos + 1)) yield return j;
18         Swap(ref arr[i], ref arr[pos]);
19     }
20 }
21 
22 static void Main(string[] args)
23 {
24     foreach (var i in Perm(new int[] { 1, 2, 3, 4 }, 0))
25     {
26         Console.WriteLine(string.Join(",", i.Select(j=>j.ToString()).ToArray()));
27     }
28 }