时间戳

首页 > 解决方案 > 获得所有可能的限制组合的算法

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

问题描述

我有数字 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

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

标签： mathcombinationsrestriction

解决方案

为了使事情更有效（并且假设解决方案比排列少得多），一个想法是：

  • 一一生成所有排列。
  • 不要以通常的方式解释排列，而是将其解释为告诉每个数字它将去到哪个位置。因此，给定一个排列(3, 2, 0, 1)，将其解释为 0 到 pos 3，1 到 pos 2，2 到 pos 0，3 到 pos 1（所以，逆排列: (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]

推荐阅读