执行多重求和

Question

我正在尝试在代码 C++ 中执行多重求和，但我不知道如何编写代码来执行多个 for 。 $$\sum_{S_1=\pm1}...\sum_{S_N=\pm1}(\Pi_{i=1}^{N-1}e^{S_iS_{i+1})}$$ 正如你所看到的，如果我尝试手动实现这一点，我应该为大 pi 编写 N 个，然后再编写 1 个，那么如何减少 N 个 for，这样我只需要 3 个，其中一个表示我想要的 for 的数量重复，另一个用于求和，最后一个用于乘法。 请帮忙

我脑子里唯一的想法是： 对于 S1 = [-1,1] 对于 S2 = [-1,1] 。 。 。 。 对于 SN = [-1,1]

Answer 1

虽然这不是你真正要求的，但你可以简化

\Pi_{i=1}^{N-1}e^{S_iS_{i+1})

到

e^(\sum_{i=1}^{N-1} S_iS_{i+1})

因此您只需对每组 S_i 值进行一次求幂。

我认为你的问题与可变数量的嵌套 for 循环有关。处理这个问题的一种简单方法是为 N 的每个可能值编写一个函数，但这很冗长并且容易受到批评。

我将如何解决这个问题，使用无符号整数 U 的位来表示有符号的 S_i，如下所示。我还没有测试过这个，所以它没有保修，但希望你能明白它的要点。

S_i = (U & (1 << i)) >> i // Get the ith bit

S_i = 2*S_i - 1 // Convert to -1, 1

这样你只需要2个for循环。

bigsum = 0

for (U = 0; U < (1 << N); U++)

  exponent = 0

  for (i=1; i<N; i++)

    exponent += S_iS_{i+1}
   
  bigsum += e^exponent     
 

您将需要使用超过 maxN 位的整数类型。

Answer 2

正如西蒙所说：

\Pi_{i=1}^{N-1}e^{S_iS_{i+1})

可表示为：

e^(\sum_{i=1}^{N-1} S_iS_{i+1})

我们正在对所有 i 的每个可能的

S_i

分配进行评估，并对结果求和。请注意，总和

\sum_{i=1}^{N-1} S_iS_{i+1}

表示序列

S_i

中匹配的连续值的数量减去不匹配的连续值的数量。例如，

[1, 1, -1, 1]

生成

(1*1 + 1*-1 + -1*1) = -1

。有一个匹配的连续对

(1, 1)

和两个不匹配的连续对

(1, -1)

和

(-1, 1)

，产生相同的结果

1 - 2 = -1

。

给定序列中匹配的连续对

A

的数量可以根据不匹配的

B

的数量来计算：

A = N - 1 - B

。这意味着从

B

我们可以计算出指数的值：

A - B = N - 1 - 2*B

。

值

B

只能取区间

[0, N)

内的值。因此，我们可以尝试做一些更聪明的事情，而不是迭代所有可能的分配，计算每个

B

。我们可以尝试计算有多少个赋值产生给定的

B

，迭代

B

的每个可能值，并跳过实际的赋值。请注意，每个不匹配对的相对位置并不重要，连续匹配对的数量也不重要。例如：

[1, 1, -1, 1, -1]

具有相同数量的匹配/不匹配，因此与

[-1, 1, -1, 1, 1]

和

[1, -1, 1, 1, -1]

的总和相同。我们能做的就是将连续匹配的

S_i

分组为块：

[(1, 1), (-1), (1), (-1)]

。每个具有

S_i

非匹配连续对的

B = k-1

序列都可以被划分为

k

均匀部分，如下所示。

现在我们需要计算

N

，对于

k

中的

[1, N)

，有多少种方法可以创建统一的有序k分区。这是标准的星形和条形组合问题；我们只需要从

k-1

中选择

N-2

即可。只是为了完全清楚：

x choose y = nck(x, y) = x! / ((x-y)! * y!)

我们不能忘记的一个小细节：在每个分区中，我们声称连续的

-1

或

1

都有统一的部分。给定两个相邻部分不能同时包含

1

或同时包含

-1

，例如

[(1, 1, 1), (1, 1)]

，第一部分的值选择决定了其余部分的分配。这意味着第一部分提供了我们唯一的自由度，对于任何分区，我们都必须考虑两个选项：一个以

1

部分开头，另一个以

-1

开头。因此，实际上，具有

B

不匹配连续对（

B+1

部分）的作业计数将为

2 * nck(N-2, B)

。

现在，对于

B

的每个值，我们可以计算相应的赋值次数，乘以指数，并计算整体表达式的值。

2*\sum_{B=0}^{N-2}nck(N-2, B)e^(N-1-2*B)

nck(N-2, B)

计算可以在

O(1)

时间内完成，方法是从先前的循环迭代中构建计算，仅使用单个乘法和除法来计算新值。相同的策略可用于指数的计算。这意味着整个计算可以在

O(n)

时间内完成。