CODEWITHSUNDEEP
algorithmpermutation
robinwhy
robinwhy

Reputation: 41

How to construct one arithmetic free permutation for each n?

For some fixed integer N, an array A[1..N] is an arithmetic-free permutation if

  1. A is a permutation of { 1, ... , N }; and
  2. for every 1 ≤ i < j < k ≤ N, the elements A[i], A[j], A[k] (in order) do NOT form an arithmetic progression. That means, A[j] - A[i] ≠ A[k] - A[j]

Give an algorithm which, given N, returns an arithmetic-free permutation of size N in O(N log N) time. It is guaranteed that arithmetic-free permutations exist for all positive integers N.

Upvotes: 4

Views: 424

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

There is a good answer at https://leetcode.com/articles/beautiful-array/

Say a < b < c and b - a = c - b. Then

2 * b = a + c

Since 2 * b is always even, to break any progression, a and c must have different parity. But grouping odds to one side and evens on the other is not enough since if we have more than 4 numbers, we could generate an arithmetic progression within one of the groups.

This is where we can use the recursive idea in the article to break it. One way I understand it is to consider that if we have a solution for array size N, because the arithmetic progression depends on differences between the numbers, we can map a given solution by an arithmetic function to the same effect:

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]

Therefore all we need to do is map a smaller solution once to the even numbers and once to the odds and group them separately. (Separating the groups limits the problem to breaking the arithmetic progression in each group since, as we've shown, no progression, (a, b, c), would rely on a and c of different parities.)

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]

Upvotes: 2

David Eisenstat
David Eisenstat

Reputation: 65458

Construct the bit-reversal permutation for the next highest power of two and drop out the numbers that don't belong. There are several ways to do this in O(n log n) time. I'm not going to write a formal proof in case this is homework, but the general idea is to look at the lowest order bit where A[i], A[j], and A[k] are not all the same and observe that the two that agree are adjacent.

Upvotes: 2

Related Questions