我正在阅读一篇数学文章,其中包含以下引理:
给定任何实数序列 a_{1}, ..., a_{n},让我们将它们的累积和表示为 s_{1}, ..., s_{n}。 a_{1}, ..., a_{n} 存在唯一的循环排列 sigma,使得
for all k: s_{k}(sigma) <= s_{n}/n * k
(即,部分和的序列位于连接 (0, 0) 和 (n, s_{n}) 的线下方。
我决定编写一个Python代码来说明这个引理(它将绘制随机序列的部分和序列的图,以及唯一排列的部分和序列的图,保证其存在由引理)。这是代码:
randarr = np.random.randn(9)
tot_arr = np.array([0, *randarr])
init_cumsum = np.cumsum(tot_arr)
mean_array = np.array([ n * init_cumsum[-1]/(len(init_cumsum) - 1)\
for n in range(len(init_cumsum)) ])
def permuted(k):
return np.cumsum([0, *np.roll(randarr, k)])
fig, ax = plt.subplots(figsize=(5, 3))
ax.plot(np.arange(0, 10, 1), init_cumsum)
ax.plot(np.arange(0, 10, 1), mean_array, '--')
for k in range(1, 10):
if (mean_array >= permuted(k)).all() :
ax.plot(np.arange(0, 10, 1), permuted(k), label="correct permutation")
plt.legend()
break
else:
print(tot_arr)
plt.show()
由于我是一个简单的人,所以我没有按照引理描述构建正确的排列,而是迭代所有循环排列(除了第一个循环排列),并绘制满足条件的排列。然而,有时Python认为没有循环排列满足条件(即初始排列不是正确的排列,但代码无法在其余排列中找到正确的排列)。
我让它打印这样的随机序列,然后尝试插入它们而不是随机序列。当我这样做时,代码很容易找到正确的排列并绘制它。我看不到第一次生成此类序列时代码其余部分获得的数据与在接下来的手动输入时运行的数据之间的差异,所以,我猜,我的代码中的某些内容与我的工作方式不同期望,这解释了为什么我使用相同的输入数据获得不同的结果。但是,我不明白哪里出了问题。
编辑:
程序中断的序列示例:
-0.12254795 -1.18301478 1.9911016 -0.67975716 -0.53877141 0.49170832 -1.08431192 1.03930656 -0.14305318
-0.98415686 -0.19698914 1.25619013 -0.31378433 1.45470612 0.04794845 -2.12723127 -0.69520889 0.28457194
2.11822629 -1.2222578 0.48015473 -0.57059476 0.76872146 0.44806995 -0.76466846 0.404127 -0.35847348
-0.04126626 -2.0829324 -0.5147483 0.13324286 -2.08391787 0.00566639 2.07952122 0.83424157 0.71345859
此外,当我使用
np.random.randint(-10, 10, 9)
而不是 np.radnom.randn(9)
时,该程序似乎始终有效
我认为这可能是一个舍入误差,因为减去一个非常小的项(例如 0.1**15)然后它会产生一个解决方案;
for k in range(1, 10):
if (mean_array >= permuted(k)).all() - 0.1**15 :
ax.plot(np.arange(0, 10, 1), permuted(k), label="correct permutation")
plt.legend()