java - 用于检查二进制数组是否可以旋转以使元素总和不超过 1 的快速算法

Question

假设我有一组只包含 0 和 1 的等长数组。我的目标是找出在对任何数组进行任何旋转之后，数组的元素总和是否不会超过 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

您可以将此问题简化为 exact cover问题并使用一种已知的算法来精确覆盖(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-hard 问题，这意味着反向方向也会减少，因此对于可证明的最坏情况运行时间是次指数的算法没有希望。

编辑:是的，这个问题是 NP 难的。 从 3-partition 可以轻松减少我将通过示例进行演示。

假设 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，因此最终数组是一个"template"

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

强制执行 3 分区约束。