将一个整数数组转换为非负整数数组

Question

从一个整数数组开始，使其值的总和为正整数S。以下例程始终以相同数量的步骤和相同结果终止。为什么？

从数组x = [x_0，x_1，...，x_N-1]开始，使所有x_i都是整数。只要有负条目，就执行以下操作：

• 选择任何索引i，使得x_i < 0。

• 将x_i（负数）添加到x_（i-1％N）中。

• 将x_i（负数）添加到x_（i + 1％N）中。

• 用-x_i（正数）替换x_i。

此过程保持x_0 + x_1 + ... + x_N-1 = S的特性。对于任何给定的起始数组x，无论在任何步骤中选择哪个索引，经过这些步骤的次数与生成的向量相同。甚至我自己都不清楚（至少对我来说）这个过程是否会有限时间终止，更不用说具有这个好的不变特性。

例子：

取x = [4，-1，-2]并翻转x_1开始，结果为

[4, -1, -2]
[3, 1, -3]
[0, -2, 3]
[-2, 2, 1]
[2, 0, -1]
[1, -1, 1]
[0, 1, 0]

另一方面，将x_2翻转以开始执行：

[4, -1, -2]
[2, -3, 2]
[-1, 3, -1]
[1, 2, -2]
[-1, 0, 2]
[1, -1, 1]
[0, 1, 0]

并且，如果您选择在第三个数组中翻转x_2而不是x_0，则用从第三个数组开始反转的数组给出此解决方案的最终方法。 在所有情况下，6步导致[0,1,0]。

我有一个论点证明这是正确的，但对我来说似乎过于复杂（它与Coxeter groups有关）。 有人有更直接的思考方式吗？ 即使找到一个理由表明这应该终止也很好。

对于给定数组确定步骤数的任何人都将获得额外积分（无需经过过程）。

- PengOne

---

数组不应该是 [x_0, x_1, ... x_N-1] 才能使模数运算起作用吗？ - Himadri Choudhury

@Nemo：将x_1翻转得到[2,1,-2]，将x_2翻转得到[2,-2,1]，因此无论如何该过程尚未结束。 - PengOne

另外，从 [4, -2, -1] 开始。如果我选择第一个元素，我会得到 [6, 0, 1] 并在一次迭代中终止。如果我选择第二个元素，我会得到 [5, -1, 1] 并需要再进行一次迭代。我有误解这个问题吗？ - Nemo

明白了，我使用的是新的 x_i 而不是原始的 x_i。 - Nemo

我注意到在这两个例子中，绝对值之和分别为7 7 5 5 3 3 1。虽然不知道这是否有用。 - AakashM

Answer 1

我想象将负值向两个方向推送，直到它们消失。由于加法是可交换的，处理元素的顺序并不重要。

- Doug Currie

---

有趣的想法...能详细介绍一下吗？ - PengOne

我猜我小时候（很久以前！）经常在沙盒里玩。看看沙子中的山丘和山谷；如果你对称地移动沙子来填补每个洞（使用“沙子守恒”），无论你从哪里开始，结果都是相同的。 - Doug Currie

+1 非常棒的比喻...不确定它是否像我想要的那样严谨（你并不是填补空洞，而是反转土丘），但这是一个很好的思考方式。 - PengOne

你已经拥有的是一个不变量，描述了所有状态的共同属性。Doug建议的是一个变量 - 每次迭代后总是增加的东西。 - hugomg

Answer 2

我认为最简单的方法，可以看到为什么无论在每个步骤中选择哪个索引，输出向量和步数都是相同的，就是将问题看作一堆矩阵和向量乘法。对于 x 有三个分量的情况，将其视为一个3x1的向量：x = [x_0 x_1 x_2]'（其中 ' 是转置操作）。循环的每次迭代将选择翻转 x_0,x_1,x_2 中的一个，它对 x 执行的操作与乘以以下矩阵之一相同：

      -1  0  0               1  1  0                1  0  1
s_0 =  1  1  0       s_1 =   0 -1  0        s_2 =   0  1  1
       1  0  1               0  1  1                0  0 -1

当索引=0时，乘以s_0是执行的操作，s_1对应于=1，s_2对应于=2。通过这种方式，您可以将算法解释为在每次迭代中将相应的s_i矩阵乘以x。因此，在第一个示例中，在开始时翻转了x_1，算法计算：s_1*s_2*s_0*s_1*s_2*s_1[4 -1 -2]'=[0 1 0]'

您选择的索引不影响最终输出向量的事实源于s矩阵的两个有趣属性。首先，s_i*s_(i-1)*s_i=s_(i-1)*s_i*s(i-1)，其中i-1是模n计算的，n是矩阵的数量。只需要这个属性即可看到为什么在具有3个元素的示例中会得到相同的结果：

s_1*s_2*s_0*s_1*s_2*s_1=s_1*s_2*s_0*(s_1*s_2*s_1)=s_1*s_2*s_0*(s_2*s_1*s_2)，这对应于在开始时选择x_2，最后：

s_1*s_2*s_0*s_2*s_1*s_2=s_1*(s_2*s_0*s_2)*s_1*s_2=s_1*(s_0*s_2*s_0)*s1*s2，这对应于选择在第三次迭代中翻转x_0，但在开始时选择翻转x_2。

第二个属性仅适用于x具有4个或更多元素的情况。当x具有4个元素时，s_i*s_k=s_k*s_i，其中k <= i-2，再次计算i-2模n。当您考虑x具有4个元素时的矩阵形式时，此属性是显然的：

       -1  0  0  0          1  1  0  0          1  0  0  0          1  0  0  1
s_0 =   1  1  0  0   s_1 =  0 -1  0  0   s_2 =  0  1  1  0   s_3 =  0  1  0  0
        0  0  1  0          0  1  1  0          0  0 -1  0          0  0  1  1
        1  0  0  1          0  0  0  1          0  0  1  1          0  0  0 -1

第二个属性实际上是在说明您可以更改非冲突翻转发生的顺序。例如，在一个4元素向量中，如果您首先翻转x_1，然后再翻转x_3，这与首先翻转x_3，然后再翻转x_1具有相同的效果。

- gwilkins

---

很好的观察，但仍然不是证明。虽然你的转换在数学上是有效的，但s_i*s_(i-1)*s_i可能是一个合法的移动序列，而s_(i-1)*s_i*s_(i-1)不是一个合法的移动序列（因为只有负数可以翻转）。因此，在没有参考你正在操作的向量的情况下，你不能将一个替换为另一个。 - Nemo

实际上，如果s_i*s_(i-1)*s_i是有效的，则可以保证s_(i-1)*s_i*s_(i-1)也是有效的。取x=[x_0 ... x_(i-1), x_i, ... x_(n-1)]。如果s_i*s_(i-1)*s_i是有效的，则意味着x_i和x_(i-1)都是负数，因为先翻转第i个元素，然后再翻转第i-1个元素会导致s_(i-1)*s_i*x=[x_0 ... -x(i)-x_(i-1), x_(i-1), ... x_(n-1)]。如果可以翻转第i个元素（假设s_i*s_(i-1)*s_i是合法的），则第i个元素x_(i-1)是负数。因此，x_i和x_(i-1)都是负数。 - gwilkins

这是一个很好的思考方式。本质上，它与Coxeter证明相同，该证明使用仿射对称群上的Bruhat序（由s0 s1 s2生成，其中si ^ 2 = id和辫子关系si si-1 si = si-1 si si-1）。不想破坏乐趣，但移动次数就是需要多少次乘法才能回到单位元（反演数、Coxeter长度、许多其他名称）。忽略细节，这太棒了。 - PengOne

我仍然看不出这意味着步骤数是固定的，也不知道最终结果是什么。能否有人详细解释一下？“只翻转负数”的限制在这里被使用了吗？ - Nemo

在我的世界观中，这与应用si是否减少（翻转为负数）或增加（翻转为正数）长度有关（最小数量的si应用于恒等式以获得向量）。 - PengOne

Answer 3

当N被3整除时，这里有一个观察结果...可能没有用，但我想把它写下来。

设w（复数）是1的原始立方根，即w^3 = 1且1 + w + w^2 = 0。例如，w = cos(2pi/3) + i*sin(2pi/3)。

考虑和x_0 + x_1*w + x_2*w^2 + x_3 + x_4*w + x_5*w^2 + ...。也就是说，将序列的每个元素乘以连续的w幂并将它们全部加起来。

在每一步中，这个总和会发生一些适度有趣的变化。

考虑序列中的三个连续数字[a, -b, c]，其中b为正数。假设这些元素与w的幂对齐，以便这三个数字对总和的贡献为a - b*w + c*w^2。

现在对中间元素执行这一步。

在这一步之后，这些数字会对总和做出贡献：(a-b) + b*w + (c-b)*w^2。

但是由于1 + w + w^2 = 0，所以b + b*w + b*w^2 = 0。因此，我们可以将其添加到先前的表达式中，得到a + 2*b*w + c。这与我们在进行这一步之前非常相似。

换句话说，这一步只是向总和中添加了3*b*w。

如果三个连续数字与w的幂对齐，以贡献（例如）a*w - b*w^2 + c，则这一步将添加3*b*w^2。

换句话说，无论w的幂如何与三个数字对齐，这一步都会使总和增加3*b、3*b*w或3*b*w^2。

不幸的是，由于w^2 = -(w+1)，这实际上并没有产生一个稳定递增的函数。所以，正如我所说，可能没有用处。但仍然似乎一个合理的策略是寻找每个位置的“签名”，它随着每一步单调变化...

- Nemo

---

我喜欢将向量的坐标想象成位于圆上的想法，但我不确定原始p次单位根的这个想法是否有任何用处。 - PengOne

你说得对，这与使用任何三个向量使它们的和为1是相同的。我最初将序列视为某个数字的基数下的数字，然后开始尝试“某些东西”的想法，并偶然发现了1的立方根。但这并没有真正帮助解决问题。 - Nemo