一种算法，用于找到n个整数的排列，使得对于任意两个数字a[i]和a[j](i<j)，它们的平均值不在它们之间
给定一个由 n 个整数组成的数组，我们如何有效地重新排列其中的数字，使得对于任意两个数字 a[i] 和 a[j] (i < j)，它们的平均值不在两个元素之间？
请注意 (i + 2) <= j < n 其中 n 是数组的长度。数字和平均值只允许使用正整数，即对于 1 和 2，平均值是 1.5，我们需要忽略它。原始数组中的数字是不同的。
让我们举个例子 - 如果给定的数组是 arr = [1, 2, 4, 7]，这不是当前状态下的有效排列，因为 arr[0] 和 arr[3] 的平均值是 4，其中 arr [2]，所以平均 4 位于 1 和 7 之间。但是 [1, 2, 7, 4] 是一个有效的排列。
我想了想，这是我能想出的解决方案，我找不到算法优化的真正范围。我遇到了一些解决方案，例如根据偶数/奇数索引递归地对数组进行分区并将它们合并回来，但它对某些输入不起作用。
from copy import copy
from collections import defaultdict
def arrange_numbers_no_avg_in_between(arr):
def permutations_helper(i):
if i == len(arr) - 1:
num_index_mapping = defaultdict(list)
for idx, num in enumerate(arr):
num_index_mapping[float(num)].append(idx)
for start in range(len(arr) - 2):
for end in range(start + 2, len(arr)):
avg = (float(arr[start]) + float(arr[end])) / 2
if any(start < idx < end for idx in num_index_mapping[avg]):
return
return copy(arr)
else:
for j in range(i, len(arr)):
arr[i], arr[j] = arr[j], arr[i]
result = permutations_helper(i + 1)
if result:
return result
arr[i], arr[j] = arr[j], arr[i]
return permutations_helper(0)
if __name__ == '__main__':
print arrange_numbers_no_avg_in_between([1, 4, 2, 7])
print arrange_numbers_no_avg_in_between([1, 201, 202, 431, 522])
print arrange_numbers_no_avg_in_between(list(range(10)))
这是我收到的输出，
[1, 2, 7, 4]
[1, 201, 202, 431, 522]
[0, 8, 4, 2, 6, 5, 1, 3, 9, 7]
我的算法的时间复杂度似乎是 O(nn!)，我将不胜感激任何对更好和有效算法的帮助。谢谢。
回答
简答
如果arr是非负ints的 Python 列表，并且数组中没有三次重复的值，则
sorted(arr, key=lambda n: f'{n:b}'[::-1])
是arr具有所需属性的排列。如果是三重重复的值，那么作为@hilberts_drinking_problem在注释观察到，没有置换具有期望的属性。
例子
>>> arr = list(range(10))
>>> arr
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> sorted(arr, key=lambda n: f'{n:b}'[::-1])
[0, 8, 4, 2, 6, 1, 9, 5, 3, 7]
更长的答案和解释
如果列表具有所需的属性，我们将其称为“闪亮”列表。（随意用你最喜欢的形容词替换“闪亮”。命名事情很难。）
然后有一些易于检查的光泽属性：
- 闪亮列表的任何子列表（保留顺序）都是闪亮的。例如，
[0, 8, 4, 2, 6, 1, 9, 5, 3, 7]是闪亮的，所以子列表[0, 4, 2, 9, 3]是闪亮的。 - 如果
arr是闪亮的并且我们k为 中的每个值添加或减去一个常量整数arr，则结果列表仍然是闪亮的。例如，[0, 8, 4, 2]是闪亮的，所以[1, 9, 5, 3]是闪亮的。 - 如果 的所有元素
arr都是偶数，那么arr当且仅当我们通过将 的每个元素减半得到的数组arr是闪亮的。例如，从[0, 8, 4, 2, 6]闪亮的事实，我们立即知道它[0, 4, 2, 1, 3]是闪亮的，反之亦然。
现在让arr我们的输入列表。然后我们可以通过以下方式找到一个闪亮的排列（如果存在）：
- 将值
arr划分为偶数值arr_even和奇数值arr_odd - 找到偶数值的闪亮排列（稍后会详细介绍）
- 找到奇数值的闪亮排列（同上）
- 将两个排列组合在一起：偶数后跟赔率
现在，如果我们在结果数组中选择任意两个数字：如果它们都是偶数，则它们都属于第一个（闪亮）部分，因此它们的平均值不在它们之间。同样，如果他们都是奇怪的。如果一个是奇数，一个是偶数，那么平均值不是整数，所以它不能在列表中。所以结果列表是闪亮的。
但是我们如何找到偶数值的闪亮排列呢？只需将数组的所有元素减半并递归。类似地，要找到奇数值的闪亮排列，请计算数组中(n-1)//2的每个的列表n并递归。
除非列表的所有元素都为零，否则递归会取得进展（列表变短，或者列表中的值变小）。在这种情况下，如果数组有 2 个或更少的元素，则数组是闪亮的，如果它有 3 个或更多的元素，则没有闪亮的排列。
这是一些代码，为了清晰而不是效率进行了更多优化：
def shiny(arr):
""" Return a shiny permutation of arr, if one exists. """
# Base case: all zeros
if not any(arr):
if len(arr) > 2:
raise ValueError("No shiny permutation")
return arr
# Recurse: divide into evens and odds
return [
2 * m for m in shiny([n // 2 for n in arr if n % 2 == 0])
] + [
2 * m + 1 for m in shiny([(n - 1) // 2 for n in arr if n % 2 == 1])
]
例子：
>>> shiny([1, 2, 4, 7])
[4, 2, 1, 7]
>>> shiny([1, 201, 202, 431, 522])
[522, 202, 1, 201, 431]
>>> shiny(range(10))
[0, 8, 4, 2, 6, 1, 9, 5, 3, 7]
但是我们可以做得更好：从递归过程来看，我们首先根据最低有效位进行分离：偶数是那些最低有效位0，然后奇数是那些最低有效位1。然后由于我们将所有内容除以二，递归的下一层根据原始数字的第二个最低有效位分开，然后是第三个最低有效位的下一级，依此类推。在极限情况下，我们所做的只是根据每个整数的二进制扩展进行排序，但最低有效位在前。
所以整个算法可以表示为一种排序，使用反向二进制扩展作为键：
>>> sorted(range(10), key=lambda n:f'{n:b}'[::-1])
[0, 8, 4, 2, 6, 1, 9, 5, 3, 7]