假设我有一组只包含零和一的恒定长度数组。我的目标是找出在任何数组旋转之后，数组的元素总和是否不超过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那么这是不可能的。
到目前为止，我能想到的方法的最佳思路是采用两个数组，找到将它们合并在一起的方法，并反转结果。然后，我们获取此结果和下一个数组，并重复此过程。但是，如果存在解决方案，则此方法无法保证找到解决方案。
我的问题是，没有尝试每一个可能的轮换，这个问题的优秀算法是什么？
你可以把这个问题减少到一个 确切的封面 问题并使用已知的精确覆盖算法之一（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分区约束。
如果问题出现在P或NP难以解决的问题上，我仍然未定。肯定有很多数学结构可供利用。。看到 大卫的回答。
但是在其他人提供一个很好的解决方案之前，这里有一些理论上可行的东西，也可能在实践中起作用。
基本思想是：将其表述为 SAT-问题 并使用 非常有效的求解器 对于这种组合问题。
我们在这里使用的SAT-solver类型是 基于CDCL的求解器 这是完整和健全的（他们会找到一个可行的解决方案或证明没有！）。
分析（天真的方法）
虽然SAT求解通常是NP难的，但通常可以解决具有数百万个变量和约束的实例。但这并不能保证这会在这里起作用。没有测试就很难说，遗憾的是，没有提供测试数据。
配方很简单：
N * M 二进制变量：
N marks the data-row; M the roation/shift value
- 答：预处理所有可能的成对冲突
- B：添加约束，使用每行的至少一个配置
- C：添加禁止冲突的约束
对于 N=100 行 M=100 cols，将有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]]
我将每个位集合视为（足够大）整数。
说我有这样的整数集合 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，因此我们不能将剩余元素移位到累加器已经占用的位。因此，我们必须从掩码中清除累加器占用的位。这大大减少了组合，这就是为什么首先对最大的bitCount进行排序是有益的。
其次，守卫 (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