找到数字 1 到 N 的排列，使得排列中任意两个数字的平均值不会出现在它们之间

Question

例如：对于 N = 4，[1,3,2,4] 是一个解排列，但 [1,4,2,3] 不是，因为 2 出现在 1 和 3 之间。

我正在阅读这个解决这个问题的博客 post。 https://kartikkukreja.wordpress.com/2014/11/04/interesting-problem-multiple-solutions/

我无法理解这个问题的分而治之方法是基于这样一个事实，即奇数和偶数的平均值不是整数，因此不需要关心。我无法理解第一次划分后的逻辑如何进行。

Answer 1

以下是如何将这个问题简化为更小的问题：

假设您输入的所有数字都是偶数。然后，把所有的数除以2求出来，最后把所有的数都乘以2。
假设您输入的所有数字都是奇数。然后，对所有数加1，然后求解，最后对所有数减1。
假设有些数字是奇数，有些是偶数。然后，先解奇数，再解偶数，将两个结果拼接起来

例如，对于给定的输入向量 (1,2,3,4,5,6,7)：

P([1,2,3,4,5,6,7]) := P([1,3,5,7]) + P([2,4,6])

P([1,3,5,7]) := P([2,4,6,8]) - 1 = 
  P([1,2,3,4]) * 2 - 1 = 
  ( P([1,3]) + P([2,4]) ) * 2 - 1 = 
  [1,3,2,4] * 2 - 1 = [2,6,4,8] - 1 = [1,5,3,7]

P([2,4,6]) := P([1,2,3]) * 2 = [1,3,2] * 2 = [2,6,4]

所以最终

P([1,2,3,4,5,6,7]) = [1,5,3,7,2,6,4]

找到数字 1 到 N 的排列，使得排列中任意两个数字的平均值不会出现在它们之间

Find a permutation of numbers 1 through N such that average of any two numbers in the permutation does not occur between them

algorithm

math

permutation