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

问：

假设我有一组只包含 0 和 1 的常量长度数组。我的目标是找出在任何数组旋转后，数组的元素总和是否会超过 1。

例如，假设我有以下三个数组：、和。我可以将第二个数组旋转一个元素，将第三个数组旋转两个元素，以获得数组，其元素和为。但是，如果我没有应用旋转，我会得到一个总和，这不符合我的要求，因为其中一个元素（3）大于 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]

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

当前启发式方法

显然，如果数组的总和（例如，长度）超过，那么这几乎是不可能的。
到目前为止，我能想到的最好的方法是采用两个数组，找到一种将它们合并在一起的方法，然后反转结果。然后，我们获取这个结果和下一个数组，并重复这个过程。但是，此方法不能保证找到解决方案（如果存在）。nn

我的问题是，除了尝试所有可能的旋转之外，解决这个问题的好算法是什么？

Java 数组算法语言无关的启发式算法

分析（幼稚方法）

虽然 SAT 求解通常是 NP 困难的，但通常可以求解具有数百万个变量和约束的实例。但这并不能保证这在这里行得通。没有测试就很难说，可悲的是，没有提供测试数据。

公式非常简单：

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

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

当然，如果你得到非常稀疏的数据，这可能会改变，这些数据允许在固定的情况下增长（在可行的实例世界中）。NM

可能有很多潜在的减少。

这里的外卖信息：

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

备注：

没有约束，在某些情况下，可能会选择两种配置。solution-reconstruction 代码不会检查这种情况（但理论上没有问题 - >只需选择一个 => 即可兼容）。<= 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]]

7赞 David Eisenstat 2/24/2018 #2

你可以把这个问题简化为一个精确覆盖问题，并使用一种已知的算法来实现精确覆盖（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 分区约束。

SequenceableCollection>>canPreventsOverlapingBitByRotatingOver: n
    "Answer whether we can rotate my elements on n bits, such as to obtain non overlaping bits"
    | largestFirst nonNul nonSingletons smallest |

    "Exclude trivial case when there are more than n bits to dispatch in n holes"
    (self detectSum: #bitCount) > n ifTrue: [^false].

    "Exclude non interesting case of zero bits"
    nonNul := self reject: [:each | each = 0].

    "Among all possible rotations, keep the smallest"
    smallest := nonNul collect: [:each | each smallestAmongBitRotation: n].

    "Note that they all have least significant bit set to 1"
    [smallest allSatisfy: [:each | (each bitAnd: 1) = 1]] assert.

    "Bit singletons can occupy any hole, skip them"
    nonSingletons := smallest reject: [:each | each = 1].

    "Sort those with largest bitCount first, so as to accelerate detection of overlaping"
    largestFirst := nonSingletons sorted: #bitCount descending.

    "Now try rotations: all the shift must differ, otherwise the shifted LSB would overlap"
    ^largestFirst checkOverlapingBitRotated: n

其中，我们将以下实用程序定义为：

SequenceableCollection>>checkOverlapingBitRotated: n
    "Answer true if the bits of my elements can be rotated on n bits so as to not overlap"
    ^self checkOverlapingBitRotatedBy: (1 << n - 1) among: n startingAt: 2 accum: self first

SequenceableCollection>>checkOverlapingBitRotatedBy: shiftMask among: n startingAt: index accum: accum
    index > self size ifTrue: [^true].
    (shiftMask bitClear: accum) bitsDo: [:bit |
        | shifted |
        shifted := (self at: index) bitRotate: bit lowBit - 1 among: n.
        ((accum bitAnd: shifted) = 0
            and: [self
                    checkOverlapingBitRotatedBy: shiftMask
                    among: n
                    startingAt: index + 1
                    accum: (accum bitOr: shifted)])
            ifTrue: [^true]].
    ^ false

这需要额外的解释：shiftMask 中的每一位都表示（排名）可能的移位。由于累加器已经占用了多个位，并且每个元件的LSB为1，因此我们不能将剩余元件移位到累加器已经占用的位。因此，我们必须从掩码中清除累加器占用的位。这大大减少了组合，这就是为什么首先对最大比特数进行排序是有益的。

其次，守卫正在尽快切断递归，而不是生成无用的组合并测试后验的不可行性。(accum bitAnd: shifted) = 0

然后我们有了这些小的实用程序：

Integer>>bitRotate: shift among: n
    "Rotate the n lowest bits of self, by shift places"
    "Rotate left if shift is positive."
    "Bits of rank higher than n are erased."
    | highMask lowMask r |
    (r := shift \\ n) = 0 ifTrue: [^self].
    lowMask := 1 << (n - r) - 1.
    highMask := 1 << n - 1 - lowMask.
    ^((self bitAnd: lowMask) << r)
        bitOr: ((self bitAnd: highMask) >> (n - r))

Integer>>smallestAmongBitRotation: n
    "Answer the smallest rotation of self on n bits"
    ^self
        bitRotate: ((1 to: n) detectMin: [:k | self bitRotate: k among: n])
        among: n

Integer>>bitsDo: aBlock
    "Evaluate aBlock will each individual non nul bit of self"
    | bits lowBit |
    bits := self.
    [bits = 0] whileFalse: [
        lowBit := (bits bitAnd: 0 - bits).
        aBlock value: lowBit.
        bits := bits - lowBit].

它可以立即适用于这样的小型集合：

| collec bitCount |
collec := #( 2r11 2r1001  2r1101 2r11011 2r1110111 2r11001101
       2r11010010111010 2r1011101110101011100011).
bitCount := collec detectSum: #bitCount.
(bitCount to: bitCount*2) detect:
    [:n | collec canPreventsOverlapingBitByRotatingOver: n].

将回答 52，这意味着我们至少需要 52 位才能获得非重叠组合，尽管 bitCount 只有 44。

所有这些都是通过简单的位操作执行的，并且应该可以很好地扩展（一旦翻译成静态语言）。

我的 32 位解释器不是这种情况，它创建盒装的大整数，给垃圾收集器施加压力，并且需要一些时间来设置 10 组，总共大约 100 位：

| collec bitCount |
collec := (1 to: 10) collect: [:i | (1 << 18 - 1) atRandom].
bitCount := collec detectSum: #bitCount.
bitCount ->
    [ collec canPreventsOverlapingBitByRotatingOver: bitCount + 10] timeToRun.

第一次尝试花费了 75 秒，bitCount=88

更公平（稀疏）的位分布会导致更快的平均时间（仍然是可怕的最坏时间）：

| collec bitCount |
collec := (1 to: 15) collect: [:i |
    ((1 to: 4) collect: [:j | (1 to: 1<<100-1) atRandom])
        reduce: #bitAnd:].
bitCount := collec detectSum: #bitCount.
bitCount ->
    [ collec canPreventsOverlapingBitByRotatingOver: (bitCount + 10 max: 100)] timeToRun.

104->1083ms
88->24ms    
88->170ms
91->3294ms
103->31083ms

上一个：命令行参数与输入 - 有什么区别？

下一个：Java 中基于 Scratch 的运动

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

Fast algorithm for checking if binary arrays can be rotated to not have an elementwise sum over 1

评论

分析（幼稚方法）

法典

输出

评论