按照数字之和排序的算法

Question

按照数字之和排序的算法

algorithmlanguage-agnosticmath

7

我有关于算法的一个与语言无关的问题。

这来自于我看到的一个（可能很简单的）编程挑战，但是我太傻了无法解决它，但又好奇心足以让我困扰。

目标是通过交换列表中数字的位置将整数列表排序为升序。每次交换两个数字时，您必须将它们的和添加到运行总额中。挑战在于产生具有最小可能运行总额的排序列表。

示例：

3 2 1 - 4
1 8 9 7 6 - 41
8 4 5 3 2 7 - 34

虽然你可以直接给出答案，但如果可能的话，你更愿意提供正确方向上的“提示”，我更喜欢这样。

- J Cooper

7个回答

3

我假设内存是充足的，你可以在实际对象上执行排序之前模拟排序过程。一种方法（可能不是最快的）是维护一个优先队列。队列中的每个节点都由到达该节点的交换成本作为键，并包含当前项的顺序和实现该顺序的步骤序列。例如，初始时它将包含一个0成本节点，其具有原始数据排序和无步骤。运行一个循环，该循环出队最低成本的队列项，并对从该点开始的所有可能的单次交换步骤进行排队。继续运行循环，直到队列头部具有已排序列表。

- Mr Fooz

2

我手动尝试解决了其中一个示例:

1 8 9 7 6
6 8 9 7 1 (+6+1=7)
6 8 1 7 9 (7+1+9=17)
6 8 7 1 9 (17+1+7=25)
6 1 7 8 9 (25+1+8=34)
1 6 7 8 9 (34+1+6=41)

由于您需要移动数字1，因此似乎必须对问题进行详尽的搜索才能完成 - 其中的细节已经被另一位用户发布。请注意，在使用此方法时，如果数据集很大，则可能会遇到问题。

如果问题允许“接近”答案，那么您可以简单地制作一个贪心算法，将最大的项目放入位置 - 直接这样做，或者首先将最小元素交换到该插槽中。

- Raymond Martineau

1

比较和遍历显然是免费的，您可以预先计算数字必须移动的“距离”（实际上是最终排序顺序）。难题是交换算法。

尽可能减少总体交换很明显很重要。还要尽可能减少较大数字的交换。

我相信通过以无状态方式评估每个排序无法保证最优的交换过程，尽管您可能经常接近（这不是挑战）。

- HUAGHAGUAH

1

我认为这个问题没有简单的解决方案，我的方法可能不比优先队列的方法更好。

找到最小的数字N。除了N之外，任何占据彼此所需位置的数字对都应该交换。通过蛮力法组装每一组可以相互交换到其所需位置的数字集合，使得在集合内排序的成本小于用N交换集合中每个元素的成本。这些集合将包含若干个循环。在这些循环内进行交换，以便最小的数字被交换两次。使用N作为占位符，交换包括N在内的所有剩余数字，这些数字构成一个循环。

- Sparr

已经有一个被接受的解决方案，大体上是正确的答案 - 你可以通过明显的修改证明它是最优的。将某物“简化”为NP困难问题太容易了；这并不能说明原问题的难度 :P - ShreevatsaR

为什么你会说“已经”呢？我在被接受的答案发布一个小时之前就已经发布了我的答案。暂且不论被接受的答案是错误的。 - Sparr

你的假设已经有一个反例了。请看雷蒙德的分析。 - recursive

关于这个假设，是指谁的？雷蒙德的分析支持了我的答案，并且反对了被接受的解决方案和Shreevatsa的评论。 - Sparr

0

作为一个提示，这似乎涉及到动态规划；这可能不是足够精确的提示来帮助你，但我宁愿从少开始！

- Zach Snow

0

您所需支付的费用是根据交换次数而不是比较次数计算的。而且您也没有提到保持其他记录需要支付费用。

- John the Statistician

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- theycallhimtom · Accepted Answer

只需阅读前两段即可获得提示。这里有一个高效的解决方案（除非我当然犯了错误）。首先对列表进行排序。现在我们可以将原始列表写成不相交循环乘积的列表。

例如，5,3,4,2,1有两个循环，(5,1)和(3,4,2)。可以将循环视为从3开始，4在3的位置，2在4的位置，4在3的位置。最终目标是1,2,3,4,5或(1)(2)(3)(4)(5)，即五个不相交的循环。

如果我们交换来自不同循环的两个元素，比如1和3，那么我们会得到：5,1,4,2,3，用循环表示为(1,5,3,4,2)。这两个循环合并成一个循环，这与我们想要做的相反。

如果我们交换同一循环中的两个元素，比如3和4，那么我们会得到：5,4,3,2,1，用循环表示为(5,1)(2,4)(3)。一个循环被分成两个更小的循环。这使我们更接近所有长度为1的循环的目标。请注意，同一循环中的任何两个元素的交换都会将该循环分成两个循环。

如果我们能够找出交换一个循环的最佳算法，我们就可以将其应用于所有循环，并获得整个排序的最佳算法。一种算法是取循环中的最小元素，并将其与其位置相同的元素交换。因此，对于(3,4,2)，我们将2与4交换。这使我们留下一个长度为1的循环（刚刚交换到正确位置的元素）和一个比以前小一个单位的循环。然后我们可以再次应用该规则。这个算法将最小元素的循环长度-1次进行交换，而其他每个元素只交换一次。

将长度为n的循环转换为长度为1的循环需要n - 1个操作。每个元素必须至少操作一次（考虑要排序的每个元素，它必须移动到其正确的位置）。我提出的算法对每个元素进行了一次操作，这是所有算法都必须执行的，然后每个其他操作都在最小元素上执行。没有算法可以做得更好。

该算法需要O(n log n)来排序，然后需要O(n)来处理循环。解决一个循环需要O(循环长度)，所有循环的总长度为n，因此循环操作的成本为O(n)。最终运行时间为O(n log n)。