用于检查二进制数组是否可以旋转到不具有1的元素和的快速算法

Question

假设我有一组只包含零和一的常量长度数组.我的目标是找出在任何数组旋转之后,数组的元素总和是否不超过1.

例如,假设我有以下三个数组:[1, 0, 0, 0], [1, 0, 1, 0]和[1, 0, 0, 0].我可以将第二个数组旋转一个元素,将第三个数组旋转两个元素以获得数组[1, 0, 0, 0], [0, 1, 0, 1], [0, 0, 1, 0],其中元素的总和是[1, 1, 1, 1].但是,如果我没有应用旋转,我会得到一个总和[3, 0, 1, 0],这不符合我的要求,因为其中一个元素(3)大于1.

现在,我的问题是,确定这对于任意数量的数组是否可行的快速方法是什么？例如,无法旋转[1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 1, 0]以使总和的元素不超过1.

目前的启发式方法

显然,如果数组的总和(例如长度n)超过n,那么这是不可能的.
到目前为止我能想到的方法的最佳思路是采用两个数组,找到将它们合并在一起的方法,并反转结果.然后,我们获取此结果和下一个数组,并重复此过程.但是,如果存在解决方案,则此方法无法保证找到解决方案.

我的问题是,没有尝试每一个可能的轮换,这个问题的优秀算法是什么？

Answer 1

你可以将这个问题简化为一个精确的覆盖问题,并使用一种已知算法进行精确覆盖(Knuth的算法X,整数线性编程,SAT求解为sascha提醒我,可能是其他人).减少涉及创建每个输入阵列的所有旋转并使用指示器扩展它们以确保选择恰好一个旋转.例如[1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 0],对于实例,确切的封面实例是

[1, 0, 0, 0; 1, 0, 0]  # from [1, 0, 0, 0]
[0, 1, 0, 0; 1, 0, 0]
[0, 0, 1, 0; 1, 0, 0]
[0, 0, 0, 1; 1, 0, 0]
[1, 0, 1, 0; 0, 1, 0]  # from [1, 0, 1, 0]
[0, 1, 0, 1; 0, 1, 0]
[1, 0, 0, 0; 0, 0, 1]  # from [1, 0, 0, 0]
[0, 1, 0, 0; 0, 0, 1]
[0, 0, 1, 0; 0, 0, 1]
[0, 0, 0, 1; 0, 0, 1]
[1, 0, 0, 0; 0, 0, 0]  # extra columns to solve the impedance mismatch
[0, 1, 0, 0; 0, 0, 0]  # between zeros being allowed and exact cover
[0, 0, 1, 0; 0, 0, 0]
[0, 0, 0, 1; 0, 0, 0]

我有一种感觉,你的问题是NP难的,这意味着反向方向也有减少,因此对于可证明最坏情况运行时间是次指数的算法没有希望.

编辑:是的,这个问题是NP难的.我将通过示例演示3分区的简单缩减.

假设3分区实例是[20, 23, 25, 45, 27, 40].然后我们制作一个二进制数组

[1, ..(20 ones in total).., 1, 0, ..., 0]
[1, ..(23 ones in total).., 1, 0, ..., 0]
[1, ..(25 ones in total).., 1, 0, ..., 0]
[1, ..(45 ones in total).., 1, 0, ..., 0]
[1, ..(27 ones in total).., 1, 0, ..., 0]
[1, ..(40 ones in total).., 1, 0, ..., 0].

我们正在寻找一个分区,其中两个部分中的每一个总和90,所以最后的数组是"模板"

[1, 0, ..(90 zeros in total).., 0, 1, 0, ..(90 zeros in total).., 0]

强制执行3分区约束.

Answer 2

我仍然不确定这个问题是 P 难问题还是 NP 难问题。肯定有很多数学结构可供利用。。请参阅大卫的回答。

但在其他人提出一个好的解决方案之前，这里有一些在理论上可行并且在实践中也可能可行的方法。

基本思想是：将其表述为SAT 问题，并使用非常有效的求解器来解决此类组合问题。

我们在这里使用的 SAT 求解器类型是基于 CDCL 的求解器，它们是完整且可靠的（它们会找到可行的解决方案或证明不存在！）。

分析（朴素方法）

虽然 SAT 求解一般来说是 NP 难的，但通常可以求解具有数百万个变量和约束的实例。但这并不能保证这在这里有效。如果没有测试就很难说，遗憾的是，没有提供测试数据。

公式很简单：

• N * M二元变量：
  • N marks the data-row; M the roation/shift value
• A：预处理所有可能的成对冲突
• B：添加每行至少使用一个配置的约束
• C：添加禁止冲突的约束

对于N=100列行M=100，将有 4950 个有序对，每个M*M (pairwise rotation-combinations)对都相乘。因此存在<= 4950 * 100 * 100 = 49.500.000冲突检查（这在慢速语言中甚至是可行的）。这也是冲突约束数量的上限。

当然，如果您的数据非常稀疏，并且允许在固定的N情况下增长M（在可行的实例世界中），那么这可能会改变。

可能有很多潜在的减少可能。

这里的要点是：

• 预处理需要大量工作（渐近！），并且该方法基于数​​组长度小于 100 的注释
• SAT 求解在传播方面非常非常快，如果是 P 或 NP 困难，我们提供的约束在传播效率方面非常强大
• 建议根据经验（根据您的数据）进行测试！

评论：

没有<= per row限制，在某些情况下可能会选择两种配置。解决方案重建代码不会检查这种情况（但不存在理论上的问题 -> 只需选择一个 => 将兼容）。

代码

from pyCadical import PyCadical  # own wrapper; not much tested; @github
import itertools
import numpy as np

""" DATA """
data = np.array([[1, 0, 0, 0],
                 [1, 0, 1, 0],
                 [1, 0, 0, 0]])

""" Preprocessing """
N = len(data)
M = len(data[0])

conflicts = []
for i, j in itertools.combinations(range(N), 2):
    for rotA in range(M):
        for rotB in range(M):
            if np.amax(np.roll(data[i], rotA) + np.roll(data[j], rotB)) > 1:
                conflicts.append((i, j, rotA, rotB))
conflicts = np.array(conflicts)

""" SAT """
cad = PyCadical()
vars = np.arange(N*M, dtype=int).reshape(N,M) + 1

# at least one rotation chosen per element
for i in range(N):
    cad.add_clause(vars[i, :])  # row0rot0 OR row0rot1 OR ...

# forbid conflicts
for i, j, rotA, rotB in conflicts:
    cad.add_clause([-vars[i, rotA], -vars[j, rotB]])  # (not rowIrotA) or (not rowJrotB)

""" Solve """
cad.solve()

""" Read out solution """
sol = cad.get_sol_np().reshape(N, M)
chosen = np.where(sol > 0)

solution = []  # could be implemented vectorized
for i in range(N):
    solution.append(np.roll(data[i], chosen[1][i]))

print(np.array(solution))

输出

[[0 1 0 0]
 [1 0 1 0]
 [0 0 0 1]]