江苏龙网

  1. 首页 > 生活 > >

怎样遍历限制了部分顺序的全排列( 二 )


当然这里已经不仅仅是个数相等了，所要求的全排列其实就是对应有向无环图的全部拓扑序。

回到原题，如何产生这样的全排列？
既然已经同一些经典问题关联起来了，还是直接google吧：
对于情况1:
How to generate all the permutations of a multiset?
情况2:
How to get all the solutions of topological sorting

■网友
随手写的，没有检查，自己保证输入，用法，在 require 第三个参数里写上要求的顺序：
#include \u0026lt;iostream\u0026gt;#include \u0026lt;algorithm\u0026gt;#include \u0026lt;vector\u0026gt;template \u0026lt;class Iter, class T\u0026gt;bool require(Iter first, Iter last, std::initializer_list\u0026lt;T\u0026gt; list){ if (list.size() \u0026lt; 2) { return true; } Iter f = std::find(first, last, *list.begin()); for (auto i = list.begin() + 1; i != list.end(); ++i) { Iter s = std::find(first, last, *i); if (s \u0026lt; f) return false; f = s; } return true;}int main(){ std::vector\u0026lt;int\u0026gt; v{ 1,2,3,4,5 }; do { if (require(v.begin(), v.end(), { 1,2,3 })) { std::for_each(v.begin(), v.end(), (int v) {std::cout \u0026lt;\u0026lt; " " \u0026lt;\u0026lt; v; }); std::cout \u0026lt;\u0026lt; "\"; } } while (std::next_permutation(v.begin(), v.end()));}输出：
1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 1 2 4 5 3 1 2 5 3 4 1 2 5 4 3 1 4 2 3 5 1 4 2 5 3 1 4 5 2 3 1 5 2 3 4 1 5 2 4 3 1 5 4 2 3 4 1 2 3 5 4 1 2 5 3 4 1 5 2 3 4 5 1 2 3 5 1 2 3 4 5 1 2 4 3 5 1 4 2 3 5 4 1 2 3.


推荐阅读


上一篇：为啥用matlab取余会出错

下一篇：除 PHP 外，马克·扎克伯格还掌握哪些编程语言