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

Question

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

1. A 是 { 1, ... , N } 的排列;和
2. 对于每个 1 ≤ i < j < k ≤ N , 元素 A[i] , A[j] , A[k] (按顺序)做NOT形成一个算术进展。这意味着，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] 不完全相同的最低位，并且观察到同意的两个是相邻的。