精确覆盖样本

包含一些精确覆盖样本及其解决方案。

安装

pip install exact-cover-samples

用法

问题

from exact_cover_samples import problems

problems 是一个具有以下结构的字典

{ "shortname": function, ... }

其中 shortname 是一个字符串，而 function 是一个函数，该函数返回一个具有以下结构的字典

{
    "shortname": str,               # short name of the problem
    "name": str,                    # long name of the problem
    "data": np.ndarray,             # of ndim=2 and dtype=bool
    "solutions": list[list[int]]    # each solution is a list of indices in data
}

在某些情况下 solutions 也是一个 nd-array - 以下是如何规范化以比较解决方案。

摘要

您可以通过运行以下代码来显示可用的问题的摘要

from exact_cover_samples import summary

summary()

将显示所有已知问题

# you can also filter a bit
summary("pent")
->
the problems whose name contains 'pent' are:
===================== p3x20 ======================
size = (1236, 72),  8 solutions full_name=pentominos-3-20
===================== p4x15 ======================
size = (1696, 72),  1472 solutions full_name=pentominos-4-15

规范表示

from exact_cover_samples import problems, canonical

p = problems["knuth2000"]()
s = p["solutions"]
type(s)
-> list
type(s[0])
-> tuple
type(canonical(s))
-> set

p = problems["p8x8"]()
s = p["solutions"]
type(s)
-> numpy.ndarray
type(canonical(s))
-> set

因此，只要您的代码产生解决方案为一个可迭代的迭代，您应该能够使用 canonical 来比较它们，如下所示

# import this module
import exact_cover_samples as ecs
# import a solver module
from exact_cover_py import exact_covers

# get a problem
p = ecs.problems["knuth2000"]()
# get the expected solutions
expected = p["solutions"]
# get the computed solutions
computed = exact_covers(p["data"])
# compare them
assert ecs.canonical(expected) == ecs.canonical(computed)

因此，您可以通过简单地迭代 problems 中的问题，并将预期的解决方案与计算出的解决方案进行比较，来为您的精确覆盖求解器编写一个非常不错的测试套件。