2

我有一个数组形式的有序序列。例如

original_order = [1,2,3,4,5,6,7,8,9,10]

我想知道如何以最大的顺序对原始顺序重新排序。具体来说，我想知道在运行以下代码时，什么顺序会给出最大“分数”：

简而言之，当与 original_order 序列中的位置进行比较时，以下计算序列中的每个值在重新排列的序列（称为重新排列的数组）中“移动”的距离。然后，它将每个值的差异（移动的距离）相加，以给出重新排列的“顺序差异”的总体得分。有人告诉我，我计算的这个“分数”可以定义为两个序列之间的序数相似度（原始顺序和重新排列）。

我认为可以通过将重新排列的顺序作为反转的原始顺序运行代码来获得最高分数。我还没有找到比这更高的分数的重新排列方法，但如果有人认为我错了，请告诉我（对于上面的示例 original_order，这将是 max_score = 50）。我认为没有其他序列顺序的重新排列可以给出更高的分数（尽管有其他顺序给出相同的分数）。

position = original_order.map{|x| rearranged.index(x)} #works out the index of original_order values in rearranged
index_values = Array(0..(original_order.length - 1)) # array of index values for original_order
both = []
both << position
both << index_values
difference = both.transpose.map {|x| x.reduce(:-)} # taking away old position from new position, to find the distance that the value has "moved" when re-ordered
difference_abs = []
difference.each do |i|
    difference_abs << i.abs
end
score = difference_abs.inject(:+)

我想知道的是：

  1. 如果我的假设是正确的，即无论序列数组的长度如何，颠倒的顺序总是会给出最高的分数

  2. 对我的代码的作用的数学解释，以及为什么简单地颠倒原始顺序会给出最高分

  3. 如果序数相似性是定义我的分数指标的准确方法，如果不是，什么是？

此外，欢迎任何有关简化我的代码的提示。

4

1 回答 1

1

该问题可以建模为分配问题。

如果原始数组是 {1, 2, 3, 4}，那么在最终数组中，有 4 个位置需要每个位置填充一个元素。这会产生一个具有相应分数的 4x4 分配矩阵。 

  positions
   1 2 3 4 
1  0 1 2 3
2  1 0 1 2
3  2 1 0 1
4  3 2 1 0

通过将分数取反并将所有元素加 3 来将分数转换为成本（尽管正如所指出的，添加常数不是必需的）。

  positions
   1 2 3 4 
1  3 2 1 0
2  2 3 2 1
3  1 2 3 2
4  0 1 2 3

您应该能够应用匈牙利算法来解决上述分配问题。请注意，应有超过 1 个解决方案。

编辑：正如 Cary Swoveland 所指出的，上述问题可以通过普通的 LP 求解算法快速解决，例如修改后的 Simplex，其中变量不必是整数。

于 2013-10-14T16:33:25.293 回答