algorithm - 使用有限的堆栈操作进行排序

Question

我正在研究一台分选机，为了减少复杂性，我想把运动部件保持在最低限度。我的设计如下：
1个输入堆栈
2+输出堆栈
启动时，机器已经知道所有项目、当前订单和所需订单。
机器可以将一个项目从输入堆栈的底部移动到它选择的输出堆栈的底部。
机器可以将所有项从输出堆栈移到输入堆栈的顶部。这叫做“回报”（在我的机器中，我计划由用户完成此操作。）
机器只访问堆栈的底部，除了通过返回当堆栈返回到输入时，“new”项将是输入中的最后一个项这也意味着，如果机器将一组项从输入移动到一个输出，则这些项的顺序是相反的。
机器的目标是从输入堆栈中获取所有项，并最终按排序顺序将它们全部移到输出堆栈中。第二个目标是将“堆栈返回”的数量减少到最小，因为在我的机器中，这是需要用户干预的部分。理想情况下，机器应该在没有用户帮助的情况下尽可能多地进行排序。
我遇到的问题是，我似乎找不到合适的算法来进行实际排序几乎所有我能找到的算法都依赖于能够交换任意元素分布/外部排序似乎很有前途，但我能找到的所有算法似乎都依赖于一次访问多个输入。
由于机器已经知道所有的项目，我可以利用这一点，并排序所有项目“在内存中”。我尝试了从未排序状态到排序状态的“路径查找”，但我无法让它真正收敛到一个解决方案（它通常只是在一个循环中来回移动堆栈。）
最好，我想要一个解决方案，工作与至少2个输出堆栈，但能够使用更多，如果可用。
有趣的是，这是一个可以用标准扑克牌玩的“游戏”：
你想整理多少就拿多少（我通常得到13件西装。）
把它们洗牌放在你的手上。决定你得到多少输出堆栈。
有两个有效的移动：
您可以移动最前面的卡在您的手，并把它放在任何输出堆栈的顶部。
你可以把一个输出堆栈中的所有卡片都捡起来，放在你手上的卡片后面。
当卡片在输出堆栈中排列整齐时，您就赢了你的分数是你捡一堆的次数分数越低越好。

Answer 1

这可以在O(log(n))将输出返回到输入中完成。如果2 ceil(log_2(n)) - 1，则返回的值不超过1 < n。
我们调用输出堆栈A和B。
首先考虑最简单的算法我们把最小的卡片放在B上，其余的放在A上，然后把A放在输入端，然后重复。通过n后，您将按顺序排列它们。效率不高，但很管用。
现在我们能不能做到每次出两张牌如果我们有卡片1，4，5，8，9，12在上半部分和下半部分，然后第一次通过将在卡2之前找到卡1，将其反转，第二次在卡4之前找到卡3，将其反转，依此类推。每张卡2张。但是，通过1次传递和2次返回，我们可以将所有想要的卡放在堆栈A的上半部分，其余的放在堆栈B上，返回堆栈A，返回堆栈B，然后开始提取。这需要通过2 + n/2关。
每张卡4张怎么样好吧，我们要把它分成四分之一。最上面的四分之一有卡1，8，9，16，…第二节有2，7，10，15，…第三个有3，6，11，14，…。最后一个有4，5，12，13，…。基本上，如果你在处理它们，你按顺序处理前4个，后4个反过来，下一个按顺序处理。
我们可以把他们分成两节我们能想出怎么去那里吗？好的，向后走，第二次传球后我们希望A有2，1节。B有四、三个季度然后我们返回A，返回B，我们就是黄金。所以在第一次传球后，我们希望A有2，4，B有1，3，返回A。
转过来向前看，在传球1中，我们把组2，4放在A上，1，3放在B上。返回A，返回B。然后在传球2中，我们把组1，2放在A上，3，4放在B上，返回A，返回B。然后我们开始交易，每次传球我们得到4张牌。现在我们使用4 + n/4返回。
如果你继续向前逻辑，在3次通过（6次返回）中，你可以找出如何在提取阶段每次通过8张卡。在4次传球（8次回传）中，每次传球可以得到16张牌等等。逻辑是复杂的，但你要做的就是记住，你希望他们按顺序结束……5，4，3，2，1。从最后一个关卡到第一个关卡，都要倒过来想想你是怎么做到的。然后你有你的前进算法。
如果你玩数字，如果n是2的幂，那么你同样可以用log_2(n) - 2返回的2 log_2(n) - 4传球，然后用4返回的3传球来进行2 log_2(n) - 1抽射，或者用log_2(n) - 1返回的2 log_2(n) - 2传球，然后用2返回的1抽射。（当然，这是假设2 log_2(n) - 1足够大，可以如此分割。这意味着第二个版本的算法是“不是1”。）如果n，我们很快就会看到选择前一个版本的算法的一个小原因。
好吧，如果你有2的倍数可以得到，那就太好了但如果你有10张牌呢？好的，插入想象的卡片，直到我们达到最接近的2次方，四舍五入。我们遵循算法，只是不做我们在虚卡上应该做的操作，我们得到了我们应该得到的精确结果，除非虚卡不在那里。
所以我们有一个一般解，不需要超过2 < n的返回。
现在我们明白为什么我们更喜欢把它分成4组而不是2组。如果我们分成4组，可能第4组只是假想的牌，我们可以跳过一个返回。如果我们分成两组，每一组都会有真正的牌，我们就无法挽回回报。
如果n2 ceil(log_2(n)) - 1，这将使我们加速1。
计算精确的规则会很复杂，我不会试图编写代码来完成它。但你应该能从这里找到答案。
我不能证明它，但有一个机会，这个算法是最优的意义上，有排列的卡，你不能做得比这更好。（当然，有一些排列可以击败这个算法。例如，如果我把所有的东西都反交给你，只提取它们比这个算法好。）然而，我期望找到给定排列的最优策略是一个NP完全问题。