如何减少数组中的移动操作次数？

Question

说我有一组数字，例如[0, 1, 2, 3, 4, 5]和我想结束一个数组，例如[2, 1, 4, 0, 5, 3]。在我看来，我有一个方法可供我使用：

move(fromIndex, toIndex)

因此，为了实现我想要的数组，我可以多次调用该方法：

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

因此，我还有一个move()操作列表，以实现我想要的结果。通过更改顺序和索引可以缩小move()操作列表的大小，最终得到相同的结果。

是否有一种算法可以在我的move()操作列表中使用，以将操作次数减少到最少？

Answer 1

我们可以创建一个图形，其元素指向需要交换的数字以到达所需位置。因此，我们将获得具有可能周期的多个图。在您的特定情况下，我们会得到

2-> 0-> 3-> 5-> 4-> 2（第一个和最后一个元素表示一个循环）

这意味着2想要与0交换以到达所需位置。类似地，0想要与3交换以到达所需位置。请注意，1不希望被交换。

现在，我们可以交换图形的两个相邻元素，将图形大小减小1.假设我们交换3和5，所以现在arr = [0,1,2,5,4,3]。现在3处于所需状态，因此我们可以从图中删除它

2->0->5->4->2

我们需要重复此过程（m-1）次以完全删除图形。这里m表示图的边数。我们可以有多个断开的图形或图形，没有周期。我们需要确保我们正在交换同一图表中的元素。最终答案是图表的所有步骤（每个组件的m-1）的总和。