快速算法检查二进制数组是否可以旋转，以避免元素总和大于1。

Question

快速算法检查二进制数组是否可以旋转，以避免元素总和大于1。

javaarraysalgorithmlanguage-agnosticheuristics

11

假设我有一组仅包含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，则显然不可能。目前我能想到的最好的方法是，取两个数组，并找到将它们合并在一起的方法，然后将结果反转。然后，我们将这个结果和下一个数组一起使用，重复此过程。但是，此方法不能保证找到解决方案。

我的问题是，在尝试每种可能的旋转之前，如何解决这个问题的好算法？

- VarmirGadkin

你的任务需要多大的N？ - sascha

非常小 - 数组的长度小于100。 - VarmirGadkin

3个回答

3

~~我仍未决定这个问题是属于P还是NP-hard。显然有很多数学结构可以利用。~~请参见David's answer。

但在其他人提出好的解决方案之前，以下方法在理论上可行且实践中也可能奏效。

基本思路是：将其制定为SAT问题并使用非常高效的求解器来解决此类组合问题。

我们在这里使用的SAT求解器是CDCL-based solvers，它们是完整和正确的（它们将找到可行的解决方案或证明不存在！）。

分析（天真的方法）

虽然SAT求解通常是NP难问题，但通常可以解决数百万个变量和约束的实例。但这并不能保证在这里能够解决。没有测试数据很难说，遗憾的是没有提供测试数据。

公式如下：

N * M 二进制变量： - N表示数据行; - M表示旋转/移位值

A：预处理所有可能的成对冲突 B：添加约束条件，至少使用每行的一个配置 C：添加禁止冲突的约束条件

对于N = 100行，M = 100列，将有4950个有序对，每个有序对乘以M*M（成对旋转组合）。因此，有<= 4950 * 100 * 100 = 49,500,000个冲突检查（即使在缓慢的语言中也是可行的）。这也是冲突约束数量的上限。

当然，如果您获得非常稀疏的数据，允许N增长而M固定（在可行实例世界中），则可能会发生变化。

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

这里的主要信息:

预处理是很费力的（渐近！）并且该方法基于评论数组的长度小于100
SAT求解在传播方面非常快，如果P或NP难度，则我们提供的约束类型在传播效率方面非常有效
建议在您的数据上经验测试！

备注:

每行没有<=约束条件，在某些情况下可能会选择两个配置。解决方案重建代码不检查此情况（但不存在理论问题->只需选择一个=>将兼容）。

代码

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]]

- sascha

0

我将把每个比特集合视为（足够大的）整数。

假设我有一个具有n位的整数集合。以下是一些Squeak Smalltalk代码，展示如何稍微减少组合：

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.

第一次尝试，bitCount=88，用了75秒。

更公平（稀疏）的位分布会导致更快的平均时间（但最差时间仍然很糟糕）：

| 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

- aka.nice

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

您可以将此问题简化为精确覆盖问题，并使用已知的精确覆盖算法之一（如Knuth的X算法、整数线性规划、SAT求解，可能还有其他算法）。简化过程涉及创建每个输入数组的所有旋转，并使用指示器扩展它们以确保选择恰好一个旋转。例如，对于实例[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-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，因此最终的数组是一个“模板”。

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

强制执行3个分区的约束条件。