使用简单的数组通过堆叠来对数字进行排序？

Question

这是一个家庭作业问题（对不起，我知道这些问题都被人忽视），但我和老师都不知道如何有效地解决问题，所以我想把它放在这里看看SO上的精彩大脑是否可以帮助我们出去了。

给出了包含随机数的未指定大小的数组。它必须按升序排列。每个元素可以移动到相邻的空白空间，也可以移动到相邻的较大元素的顶部。我需要编写一个方法来返回排序给定数组所需的最小移动次数。

这个问题被标注为“可选”，因为老师意识到问题太困难了，但我很好奇它是如何解决的。对于任何大小的数组（对于我所关心的所有长度为3的数组）都有任何建议。

编辑：谢谢指出，这是不清楚的。我使用这个数组来表示假设的真实世界情况。我们以硬币为例：它们全部放在一张桌子上，只有一定数量的“空格”可以放进去，但是它们可以放在相邻的较大的硬币的顶部，到一个相邻的空置空间（已经被大概在一堆之上移动的硬币腾空了）。

Answer 1

我认为：

• “分类”是指有留下一个堆叠
• 我们只能移动堆栈到另一个堆栈如果源堆栈中的最大数量比最小数量少目的地栈（或等同地：堆必须在顶部更小的数字排序，并在另一个的顶部移动的堆叠到另一个移动整个堆叠）

然后，有obviosly没有解决方案，如果该数组包含不止一次。此外，数量的大小并不重要，只有他们的排名。在不失一般性的情况下，我们可以假定该数组以任意顺序包含数字1..n。另外，为了确定可能的移动，只有堆栈底部的顶部很重要。因此，足以存储：

int[] bottom; 
int[] top; 

既然我们不能把堆分开，我们可能只我移动堆栈到堆栈j若bottom[i] + 1 == top[j]，否则我们将在一个无法解决的状态结束。但是，如果我们处于游戏状态，可以采取这样的行动，那么最好立即执行它，因为最终我们必须将这些堆栈结合起来，并且移动单个堆栈比移动两个堆栈便宜。

因此，唯一的自由度是如何将堆栈移动到最少的移动位置。目前，我没有看到明显的贪婪算法，因此寻找最佳解决方案可能需要将游戏位置编码为图形，并将最短路径算法应用于该图形以找到最短的移动序列。

Answer 2

我决定检查与几个假设/变化的问题，因为它使人们更有趣的问题，对我说：

1）您可以向左或向右移动从一堆的任何部分内容。

2）你可以将一个元素堆叠到一个堆上，无论它是更大，更小还是相同的大小。

3）数组被认为是只要你永远不小的数字前遇到比较大的数字，无论你如何去通过堆排序。所以_ 11 2 3排序，但_ _ 12 3是不是因为你能解释2为前1

这导致了一个非常有趣的问题，尽管这个公理：

公理A ：您进行移动的顺序无关紧要，可以通过任何方式进行重新排列，以达到相同的最终结果。

公理AB：如果阵列中有没有重复序列，然后简单地每个元件移动朝向其最终位置。

特别，我制定了一项战略，希望你可以只用当地的检查也没有递归/回溯解决这个问题，但我已经证明这是徒劳，而且以后会表现出来。

我的策略是：

1）继续从左至右寻找那被翻转错误的方式（较低的号码前一个较大的数字）对。

2A）当你找到一个，如果有一个空白处或堆栈右手值可以马上补，将其向左，直到它填满它。

2b）否则，将左边的值向右移动一个。这会造成一种情况，即您有一堆无所谓的数字 - 首先，根据1）的逻辑将向右移动的值与其新右边的值进行比较，然后再进行比较。

2bii）治疗向下比较的方式为一对相同的比较 - 移动，如果它可以适应的空白处或堆叠，否则移动较高值权，并继续留在较低的值。

实例：

1231 - >我们转向图1b左侧，因为它会适合到一个堆栈。 11 2 3 _

1321 - >我们转向3向右因为2不适合到空斑/入栈。我们将1b左移两次，因为它会适合一个空白点/适合堆叠，然后我们右移3，因为2不会适合空白点/堆叠。 1 1 2 3

1132 - >我们将3右移，因为2不能左移。我们向左移2，因为它会适合一个空的地方。 1 1 2 3

2311 - >我们将3右移，因为1a不能离开。我们将1b移两次，因为它会适合一个空的地方。我们将1a移向左边，因为它会叠加。我们将2右移，因为1a1b不能离开。我们将1a2b左移，因为它将填满空位。 11 2 3 _

然而，我们碰到与这两个起始阵列一个问题：

23411 10移动最佳，2R，3R，4R 1AL * 3 1BL * 4使11 2 3 4 _。

23111 9移动最优化，2r * 3 3r * 3 1bl 1cl * 2使_111 2 3 - 与23411策略相反！我们移动1更少，23更多，因为有更多的1，所以我们保存移动尽可能少的移动。

这表明我们不能只是做一个简单的本地比较来解决这个新问题。

我还在思考这个问题，它似乎是在一个有趣的方式不平凡的，我希望你们当中有些人喜欢与我考虑这个:)

Answer 3

编辑：因为大家似乎解决一个不同的问题，我会说明我正在解决的问题（我认为是正确的问题（不是我们都是这样））:(使用磁盘有望使事情变得更容易理解）

给定n个堆，每个堆只包含1个磁盘，按大小递增顺序排列这些磁盘。最终的结果必须是每个堆包含1个磁盘。唯一允许的操作是将单个磁盘从一个堆的顶部移动到相邻堆的顶部，但受限制的是可能不会在较小的磁盘上放置磁盘。允许将磁盘移动到空堆或将最后一个磁盘从堆中移出。总是有n个桩，因此：（1）可能不会创建新堆，因此磁盘可能不会移出原始序列的界限。 （2）空桩仍然存在，所以如果相邻的位置是空的，那么在没有移动到该位置之前，磁盘可能不会移动到该位置。

注：

具有直径x的一种磁盘=一个数x。

这可能不是最有效的解决方案，但它应该可以工作，并且可能会给某人一些工作。

这是一个纯粹的迭代过程 - 在每一步之后，我们结束所有大小为1的堆栈;这种方法可能是一个根本性的低效率。

解决方案：

我会用1，2和5来说明以下，但是这仅仅是指示大小排序，它适用于具有相同的排序任何其他的数字相同。

• 重复，直到排序：
  • （在这种情况下5）找到的最大的元素没有在正确的位置
    
    • （其实这不一定是最大的，只是什么下面的表格，但要注意不要移动元素过去，他们应该是）
  • 我们有两种情况：
    • 这是在最左边的位置，我们有两种情况：
      • 512... - 移动1权，移动5右，移动1 2左，一端与152
      • 521... - 移动1 2左，移动2权，移动1 2右键，移动5右，移动1 2左，一端与152
    • 这不是在最左边的位置，我们有两种情况：
      • ...251... - 移动1 2左，移动5右，移动1权，最终与215
      • ...152... - 移动2左，移动1右，移动1右，移动2左，一端与251（之后我们做从以前的情况步骤）

编辑2：

一个更有效的解决方案：

1. 找到最小的磁盘没有在正确的位置
2. 把它放在盘的顶部右侧
3. 将所有磁盘移动到该磁盘的左侧1位置右侧
4. 将最小的磁盘一直移动到左（直到你遇到这将已经在正确的地方更小的磁盘）

可能的预处理步骤：排序到一个单独的列表，以有效地找到最小的元素

优化：如果你是要将磁盘移动到其右侧的目标位置，而不要将磁盘右移到上一步的右侧，只需将该磁盘放在该磁盘上即可。如何在正确的时间有效地做到这一点可能会有点复杂。不执行某些步骤来提高效率也可能有所帮助。

实施例：

52413 

// put smallest disk (1) on disk to the right 
    1 
524_3 

// shift disks to the left 1 position right (3 moves - moved 4, then 2, then 5) 
    1 
_5243 

// move 1 all the way left (4 moves) 
15243 

// same as above for 2 

    2 
15_43 

    2 
1_543 

12543 

当最小的磁盘是在最右边的位置（如现在与3的情况下），这是一个有点问题。 2种方式解决它：

• 交换1和2并把1上2（1 2位右，左2，1 2个左侧位置）。然后你会有一个空位移动到3。如果少于2个较小的元素，则不是一个选项。在我们排序了更多元素之前，这些元素不应该被修复，以防我们碰到相同的情况。

• 如果我们有12453，我们可以简单地把4上5以打开3插槽（这有点延迟问题）。如果第一个没有排序的磁盘（在这种情况下为5）大于第二个（4），我们可以使用像我之前解决方案中描述的一些策略来移动元素以满足此条件。