时间戳

首页 > 解决方案 > 一种算法，用于查找 n 个整数的排列，使得对于任何两个数 a[i] 和 a[j] (i < j)，它们的平均值不在它们之间

python - 一种算法，用于查找 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!)，如果能提供更好、更高效的算法，我将不胜感激。谢谢。

标签： pythonalgorithm

解决方案

简短的回答

Ifarr是一个非负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添加或减去一个常量整数，则结果列表仍然是闪亮的。例如，是有光泽的，所以是有光泽的。karr[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]

推荐阅读