如何为每个n构造一个算术自由排列？

Question

对于某些固定整数N，数组A[1..N]是一个无算术排列，如果

1. A是{ 1, ... , N }的置换；以及
2. 对于每一个1 ≤ i < j < k ≤ N，元素A[i]、A[j]、A[k] (按顺序排列)做而不是形成算术级数。这意味着，A[j] - A[i] ≠ A[k] - A[j]

给出了一种算法，在给定的N中，在O(N log N)时间内返回N大小的无算术排列.保证了所有正整数N都存在无算术排列.

Answer 1

为第二次最高的2次方构造位反转排列，并删除不属于的数字。有几种方法可以在O(n log n)时间内做到这一点。如果这是家庭作业的话，我不会写正式的证明，但是一般的想法是查看最低阶位，其中Ai、Aj和Ak并不完全相同，并且观察到两者是相邻的。

Answer 2

在https://leetcode.com/articles/beautiful-array/有一个很好的答案

比如a < b < c和b - a = c - b。然后

2 * b = a + c

由于2 * b总是偶数，为了打破任何级数，a和c必须有不同的奇偶。但是，将概率分组到一边，在另一边均数是不够的，因为如果我们有4个以上的数字，我们可以在其中一个组内生成一个算术级数。

这就是我们可以使用本文中的递归思想来打破它的地方。我理解的一种方法是考虑到，如果我们有一个数组大小N的解决方案，因为算术级数取决于数字之间的差异，我们可以通过一个算术函数映射一个给定的解，结果是相同的：

if [a, b, c, d] works,

then [2*a, 2*b, 2*c, 2*d] works too

and so does [2*a - 1, 2*b - 1, 2*c - 1, 2*d - 1]

因此，我们所需要做的就是映射一个更小的解决方案，一次是偶数，一次是赔率，然后分别分组。(组的分离限制了在每个组中破坏算术级数的问题，因为正如我们所显示的，没有一个级数，即(a, b, c)，将依赖于不同胎次的a和c。)

N1 -> [1]

N2 -> even map N1 + odd map N1
      [2*1] + [2*1 - 1]
      [2, 1]

N3 -> even map N1 + odd map N2
      [2*1] + [2*2 - 1, 2*1 - 1]
      [2, 3, 1]
...

N6 -> even map N3 + odd map N3
      [2*2, 2*3, 2*1] + [2*2 - 1, 2*3 - 1, 2*1 - 1]
      [4, 6, 2, 3, 5, 1]