Как построить одну арифметическую свободную перестановку для каждого 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

Хороший ответ: 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]

Answer 2

Создайте перестановку битов для следующей наивысшей степени двух и отбросьте числа, которые не принадлежат.Есть несколько способов сделать это за O (n log n).Я не собираюсь писать формальное доказательство в случае, если это домашнее задание, но общая идея состоит в том, чтобы посмотреть на младший бит, где A [i], A [j] и A [k] не все одинаковы иОбратите внимание, что два, которые согласны, являются смежными.