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

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到达pos 3，1到达pos 2，2到达pos 0，3到达pos1。然后，接受或不接受排列的测试要简单得多。

这里是Python中的实现：

from itertools import permutations

num = 0
q = [0 for _ in range(8)] # create a list with place for 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)