排列成本

Question

我得到了集合{1,2,...,n}的排列.我必须通过以最小的总成本交换位于成功位置的数字来排序这种排列.交换位于连续位置的元素x,y的成本是min(x,y).

例如,如果我有排列3,1,2,4总的最小成本是3.因为我执行这些步骤((x,y)意味着用y交换x):

• (3,1),2,4结果1,3,2,4,成本最小(1,3)= 1
• 1,(3,2),4结果1,2,3,4与成本min(2,3)= 2

总费用为3.

我通过交换最小成本未排序对来尝试蛮力,直到没有未排序的对,但这种方法显然不够快.

我的问题是,如何根据我的条件找到最低的分拣成本？

Answer 1

用于对序列进行排序的连续数量交换的数量等于以相反顺序排列的对的数量.

例如

6 1 3 2 4 5

下面列出了相反顺序的对:

(6,1) (6,3) (6,2) (6,4) (6,5) (3,2)

所以

对序列进行排序的操作是:

swap(6,1) 1 6 3 2 4 5
swap(6,3) 1 3 6 2 4 5
swap(6,2) 1 3 2 6 4 5
swap(6,4) 1 3 2 4 6 5
swap(6,5) 1 3 2 4 5 6
swap(3,2) 1 2 3 4 5 6

所以操作是确定的(除非你做一些无用的操作).

您只需要按相反的顺序计算所有对(x,y),并总结min(x,y).