減少排列

Question

我需要一種算法，它可以將排列中的運行映射到單個數字，但也會減少後續數字。

因此，運行是按排序和按序排列的序列中的一組數字。在列表中，1; 2; 3; 5; 6; 4有兩次運行，1; 2; 3和5; 6。我想用一個數字來代替它們，這是最小的，所以如果在移除運行之後，我們有4個元素的置換，置換使用數字1 ... 4.在上面，我們必須減少兩次運行。第一次運行將是1,4，轉換爲2，[5; 6]轉換爲3，以保持第二個標準。如果我對減少的排列進行排序，然後從映射中展開內部元素，然後對原始排列進行排序，我將得到相同的結果。由此產生的排列不應該有任何運行。

例如（我已經強調了運行）：

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6 
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6 
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6 

現在，我越過清單，然後列出名單，分組的運行。真正的第二部分是制定一個乾淨解決方案的難點。我想到了天真的做法，好奇的是，如果任何人有一些聰明的把戲，可以做得更好，那麼我的，我在像O（2n + n日誌n），

• 替換運行head元素並將該數據插入散列表（用於可恢復性）
• 排序以創建映射到缺失數字及其排序索引。 [1; 6; 5; 4]會輸出[（1,1）;（4,2）;（5,3）;（6,4）]
• 用步驟2中創建的映射替換步驟1中的列表並更新散列表以進行翻譯。運行

通過一個例子，再次：

 
step 1: replace runs with the head element of the run and inserting data into a hash table 
    [1;3;4;2;5;6;] -> [1;3;2;5] 
step 2: sort array to create map 
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5. 
step 3: do above translation on array from step one. 
    [1;3;2;4] 

如果我排序這個置換和重建：[1; 2; 3; 4]，3-> 3; 4和4-> 5; 6我得到，1; 2; 3; 4; 5; 6。還排序。

我正在使用列表，所以功能方法將是首選。沒有必要的代碼。當然，所有的想法都是值得歡迎的。

編輯：

mweerden：

目前尚不清楚對我有什麼對測繪精確的條件。爲什麼不允許爲N次運行的置換生成置換[1,2，...，N]？你似乎更喜歡將跑步映射到跑步中的一個數字，但是（因爲這並非總是可行），你似乎允許一些自由。 -

我不喜歡跑步映射到運行中的一些（看上面！），但我需要保持一個訂購。置換[1; 2; 3 ... N] 爲一次運行，因此可以進一步降低。這就是爲什麼它是無效的。這個順序在另一個算法的進一步操作中很重要，但是單個元素可以在最後擴展以挽救原始排列。

Answer 1

記號：

• 計數從1開始
• l.i是列表l
• l+m的元素i被列出l的級聯和m
• 運行是一個最大的子列表是對一些n和m的列表[n,n+1,n+2,...,m]與n <= m

所以我們給出列表[1,2,...,N]的排列p。我們將p分成運行r_1,r_2,...,r_M，使得p = r_1+r_2+...+r_M。然後我們正在尋找q的[1,2,...,M]這樣的r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N]。

例如，如果p = [1,3,4,2,5,6]，我們有N=6，M=4，r_1 = [1]，r_2 = [3,4]，r_3 = [2]和r_4 = [5,6]。在這種情況下，我們需要q爲[1,3,2,4]爲r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6]。

請注意，q不能包含每個定義長度大於一個的運行;如果它會，然後有一個與i < M和q.i + 1 = q.(i+1)因而[1,2,...,N]子列表r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1)，但r_(q.i)+r_(q.i + 1)也是p子列表這違背該r_(q.i)和r_(q.i + 1)是運行。

現在，找一個q給予p，我們假設一個映射數據結構與O(1)插入和數字的查詢，並與O(1)追加和向前遍歷列表中的可用性。然後我們做下面的事情。

• 首先我們構建列表runheads = [r_1.1,r_2.1,...,r_M.1]。這可以通過遍歷p而輕鬆完成，同時保持當前運行。在此步驟中，我們還記得在最後獲得N時遇到的最大數字，並構建一個映射heads，其中runheads的元素爲鍵。這一步顯然是O(n)。請注意，它與heads的值無關，所以我們可以使用運行r_i作爲密鑰r_i.1的值。

• 接下來我們從1重複（幷包括）N保持值k與初始值1。對於每個值i，我們檢查i是否在heads。如果是這種情況，我們將i -> k添加到映射f並增加k。這一步也很明顯是O(n)。爲了能夠從q到p我們還可以存儲額外的映射rev與k -> i或甚至k -> runheads(i)沒有額外的大O的成本。

• 最後，我們將映射f應用於runheads的元素以得到q。再次O(n)。

舉一個例子來說明我們看p = [1,3,4,2,5,6]的情況。

• 在第一步中，我們得到runheads = [1,3,2,5]，N=6和heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }。

• 對於我們得做點什麼第二步驟中，我們四種情況：1，2，3和5。對於這些情況，我們分別具有k的值，其分別爲1,2,3和4。這意味着f將是{ 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }。 （和rev將{ 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 }或{ 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }，這取決於你選擇哪些商店。）

• 爲了得到q我們計算map(f,runheads)這是[f(1),f(3),f(2),f(5)]或者等價地，[1,3,2,4]。

所以，如果我沒有犯錯，如果數據結構滿足上述要求，這個解決方案應該是O(n)。請注意，在實踐中，使用您自己的（O(n*log(n))）解決方案實際上可能會更有用。如果您有一個大的p但只需幾次運行，排序runheads並使用它來構建映射可能會更有效。我認爲p必須是相當大的，因爲這是事實。

Answer 2

被修改爲clarificaton

步驟1：運行算法但不是隻產生一個哈希表產生由該組的頭索引的哈希表（D1）是映射到（例如，用於[3,4]，這將是3）和與該組本身

一個列表（L1）[3; 4; 6; 8; 1; 2]：

D1    L1 

3 -> [3,4]  1 -> [3,4] 

6 -> [6]  2 -> [6] 

8 -> [8]  3 -> [8] 

1 -> [1,2]  4 -> [1,2] 

步驟2：我你看看我們現在你會看到的集合，對於給定的集合，我們有我我們找到它的指數（在L1中）和Head值。正確的映射值將是它們之間尚未採用的最小整數。例如，對於[3,4]，我們會得出該值必須介於1和3之間，並且由於已經採用了1，所以相應的值爲2.考慮到由於D1由頭部索引值，如果相應的設置存在，則總是會採用較低的值。在這個例子中，[1,2]被映射爲1，所以這個鍵已經被「取走」了。因此，在僞代碼：

for (int Current = 1; Current < L1.Length; Current++) 
{ 
    GetHead(L1[Current]); 
    Index = Current; 
    While Head > Index 
    { 
    if D1.Empty(Index) 
    { 
     D1.Add(Index,D2[Current]) 
     D1.DeleteIfNotEmpty(Head); 
    } 
    else 
     Index++; 
    } 
} 

例如

• 我們採取在L1的第一個值 - > [3,4] ...
• 獲得頭= 3
• 開始上1我們查找已經被採用的D1 [1]，所以我們增加到2。
• 我們期待爲D1 [2]裏面是空的，所以我們指定D1 [2] = [3,4]，並刪除d [3]

不提供爲O（n），但像Ø第（n +的log（n））（n，用於第一步驟中，LOG（n）的用於第二）

對於上面的例子讓你：

1 -> [1,2] 
2 -> [3,4] 
3 -> [6] 
4 -> [8] 

現在，如果你有[3; 4; 8; 6; 1; 2]，這將導致

1 -> [1,2] 
2 -> [3,4] 
3 -> [8] 
4 -> [6] 

因爲它在原始數組中使用絕對排序，我不知道這是否是正確的，或者你會希望6位於索引3和8位於索引4，在這種情況下，您可能會有（n）

如果你必須預先訂購，你將有0（n + log^2（n）），這不是很糟糕（也許更少假設快速排序爲O（log n）的訂貨L1將O（日誌（log n）的）