怎样遍历限制了部分顺序的全排列
update: 之前的答案存在一个错误，现在所有的
符号都替换成
了 。 对本题而言，
其实没有对
的相对位置有任何限制，题目只要求小的数必须在前。所以限制条件中的
关系，我们可以全部忽略。另外也只有当二元关系是
这样的严格偏序关系时，才能同一个有向无环图对应（对非严格偏序关系，我们也可以加上额外的条件来使其严格偏序，比如对
要求大小相同时下标更小的在前）。
————————————
先当个计数问题来看吧，假设所有元素的集合
,集合
表示已知的顺序关系，这里
表示
。分两种情况:
1.集合B可以分解成一系列的全序关系 比如:
2.集合B中存在偏序关系 比如:
我们不知道
的关系
情况1比较简单：
这种情况只是all permutations of multiset的变体，想想看集合{a,b,c,d,e}在限制顺序 b,c,e下的全排列同多重集{a,b,b,d,b}的全排列个数是相同的，都是
。
note：对于由k种元素组合成的n元多重集，其全排列是
，这里
表示第i种元素重复的次数。
【怎样遍历限制了部分顺序的全排列】 我们只需要把集合S里在B中通过比较符号关联的元素当作同一种元素就可以得到一个对应的多元集，集合S在限制条件B下合法的排列个数就是这个多元集全排列的个数。
情况2要复杂些：
比如就
而言我们不知道
的关系，这意味着
合法的排列顺序不止一种。那么有多少种？注意到偏序关系对应有向无环图，说到给有向无环图的节点排序，那当然就是拓扑序了。所以
的合法排序个数就是拓扑序的个数。
集合S在限制条件B下的全排列个数应该是：以S为顶点集合，B为边集合所构成的图G(有向无环图)的全部拓扑序的个数，也可以先按照方法1求出对应多元集的全排列个数，然后分别乘以图G中每个连通分量的拓扑序个数。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采
- 怎样评价类似前橙会、百老汇、南极圈这样类型的离职帮抱团，对企业的积极意义和消极意义