使用簡單的數組通過堆疊來對數字進行排序？

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），我們可以使用像我之前解決方案中描述的一些策略來移動元素以滿足此條件。