如何为每个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，在N时间内返回大小为O(N log N)的无算术排列。保证所有正整数N都存在无算术排列。

Answer 1

构造bit-reversal permutation以获得下一个最高的2的幂，并删除不属于的数字。在O（n log n）时间内有几种方法可以做到这一点。如果这是作业，我不打算写一个正式的证据，但一般的想法是查看A [i]，A [j]和A [k]不完全相同的最低位。观察到两个同意的是相邻的。

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]