首页 文章

重新排列序列以最大化顺序差异，红宝石

提问于
浏览 次
2

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

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

我想知道如何根据原始顺序重新排序顺序，顺序的最大差异 . 具体来说，我想知道在运行下面的代码时，什么顺序会给出最大“得分”：

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

我认为可以通过运行带有重新排列顺序的代码作为 reversed 原始订单来获得最大分数 . 我没有找到一个比这更高分的重新排列方法，但是如果有人认为我错了请告诉我（对于上面的例子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(:+)

我想知道的是：

  • 如果我的假设反转顺序总是给出最高分数，无论序列数组的长度如何，都是正确的

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

  • 如果序数相似性是定义我的分数度量的准确方法，如果不是，那是什么？

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

ruby arrays algorithm math sequence

1 回答

  • 1

    该问题可以建模为assignment problem .

    如果原始数组是{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

    您应该能够应用Hungarian Algorithm来解决上述分配问题 . 请注意，应该有多个解决方案 .

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

    回复于

相关问题