获得所有可能的限制组合的算法

Question

我有数字 0 到 7。可能的组合必须包含所有数字。解决方案有 8 位数字。除此之外，这些规则适用：

0 comes before 1
1 comes before 3
2 comes before 3
4 comes before 5
6 comes before 7

示例解决方案：01234567、20134567

无效的解决方案：01123456 或 31204567

首先：由于这不是大学练习，而是我在编写真实程序时遇到的实际问题，我什至不确定是否存在简单的解决方案。但如果有答案，我将不胜感激。

Answer 1

为了提高效率（假设解决方案比排列少很多），一个想法是：

一一生成所有排列。
不要以通常的方式解释排列，而是将其解释为告诉每个数字它将到达哪个位置。因此，给定排列 (3, 2, 0, 1) 将其解释为 0 到位置 3，1 到位置 2，2 到位置 0，3 到位置 1（因此，inverse permutation：(2, 3, 1, 0)）。那么，是否接受排列的测试就简单多了。

这是 Python 中的一个实现，但同样的想法可以应用于任何编程语言：

from itertools import permutations

num = 0
q = [0 for _ in range(8)] # create a list to fit 8 values
for p in permutations(range(8)):
    if p[0] < p[1] < p[3] and p[2] < p[3] and p[4] < p[5] and p[6] < p[7]:
        for i, pi in enumerate(p):
            q[pi] = i
        num += 1
        print(num, q)

输出：

1 [0, 1, 2, 3, 4, 5, 6, 7]
2 [0, 1, 2, 3, 4, 6, 5, 7]
3 [0, 1, 2, 3, 4, 6, 7, 5]
4 [0, 1, 2, 3, 6, 4, 5, 7]
5 [0, 1, 2, 3, 6, 4, 7, 5]
6 [0, 1, 2, 3, 6, 7, 4, 5]
...
1257 [4, 6, 7, 5, 2, 0, 1, 3]
1258 [6, 4, 5, 7, 2, 0, 1, 3]
1259 [6, 4, 7, 5, 2, 0, 1, 3]
1260 [6, 7, 4, 5, 2, 0, 1, 3]

获得所有可能的限制组合的算法

Algorithm to get all possible combinations with restrictions

math

combinations

restriction