該算法如何生成下一個字典順序排列的工作？

Question

這是循序漸進的過程，我發現訂購辭書排列：

1. 採取預先印刷排列並找到它的最右邊的字符，這比它的下一個字符小。讓我們稱這個角色爲'第一個角色'。

2. 現在找到'第一個字符'的天花板。 「天花板」是「第一個字符」右側的最小字符，大於「第一個字符」。讓我們稱這個ceil字符爲「第二個字符」。

3. 交換上述2個步驟中找到的兩個字符。

4. 在原始索引'第一個字符'之後對子串（非遞減順序）進行排序。

來源：http://www.geeksforgeeks.org/lexicographic-permutations-of-string/

我已經寫了我的僞代碼，它和我即將開始編程現在它。我明白算法中發生了什麼，但我不確定它爲什麼會起作用。就像步驟2一樣，爲什麼天花板角色必須是「第一個字符」右側的最小字符，大於「第一個字符」「。我明白，如果你不這樣做，它是行不通的，但我不明白爲什麼它在你這樣做的時候起作用。

如果有人可以向我解釋爲什麼你需要在算法中的每一步，這將是偉大的，它會讓我更加舒適的開始我的代碼。

編輯：我應該提到我明白你爲什麼rearange的子成acsending秩序，尋找最小置換，有什麼我不明白的是步驟1和2，爲什麼你換天花板和第一charector

Answer 1

基本上我們希望增加第一個字符，我們可以從右側以儘可能小的量增加，並儘可能小的排列（我們將瞭解我們如何做到這一點），並將字符保留在右側。爲什麼這是我們想要做的是，我希望，非常合乎邏輯。如果不是這樣，它可能有助於按照數字排列（編號）的方式進行思考 - 您可以繼續添加一個數字，直到您得到該數字的另一個排列，儘管更有效的方法是神奇地找到我們需要增加的最左邊的數字以及增加它的數量，並且簡單地得到數字的最小排列，這正是該算法所做的。嗯，我們不能只是增加一個角色給任何其他角色，它需要是一個已經存在於角色中的角色。如果這個角色存在於左邊，這並不會真正起到幫助，因爲它需要改變左邊的角色，這將使我們有可能以更大的排列結束。所以我們需要在右側使用一個角色，而在此之上，它必須是比這個角色更大的最小角色。

因此，從右側開始，對於每個角色A，查看大於A的最小字符（稱爲B）。如果您找不到，請嘗試下一個字符。上面的段落解釋了我們想要增加A到B的價值。一旦我們完成了這一步，現在我們剩下2個B來解決這個問題，我們將B減少到A的值（這基本上只是交換A和B）。從這裏我們將所有東西都固定在A所在的位置。既然我們要做這個修復，那麼新的A現在可能不應該是它的位置並不重要）。

我們如何修復剩餘的字符？那麼，我們希望它們的排列最小，這就是那些排序的字符。

這需要照顧2-4步。

步驟1呢？這實際上只是算法的優化。如果我們從右邊開始找到右邊存在一個較大字符的第一個字符，那麼我們需要找到比它右側的字符小的第一個字符是否有意義，或者，更具體地說，角色在它的右邊一個位置？考慮一下987654321 - 這裏我們什麼也做不了，因爲所有的角色都比直接在右邊的角色大。

爲了舉個例子來說：

採取ABDC。

右邊存在較大字符的第一個字符是B。 最小字符大於B是C。

所以未來可能的排列的樣子：AC??（?未知）

剩下的兩個字符是D和B，這是我們需要找到的最小的排列，這是BD。所以我們把它放在一起：ACBD。

而言交換B和C - 我們需要B成爲C（從第2款），但仍然需要字符串中B它是一個有效的置換（所以我們不能只更換B與C），並且B的結尾位置並不重要，因爲在此之後，我們會找到其餘字符的最小排列。

Answer 2

該算法的主要思想是如何找到給定排列的下一個排列。 根據您編寫的鏈接，可以通過查找最後打印排列中最右側的字符比右側字符更小來完成。

證明：

表示P = P [1] P [2] P [3] .. P [N]作爲最後的印刷排列。 假設k是最右邊字符的索引，例如P [k]> P [k + 1]。根據下一個定義，下一個（P）= P [1] p [2] p [3] .. p [k + 1] p [k] p [k + 2] p [k 3] .. p [N]。假設存在P'這樣的值（P）<值（P'）<值（Next（P））。

將k'表示爲最小指數，例如P [k']！= P'[k']。

有3個選項：

• K '< K：在這種情況下，因爲值（P '）>值（P），我們得到P'[K']> P [ķ 「]。但直到k'指數，Next（P）和P是相同的，所以P'[k']> Next（P）[k']並且直到k'它們相同（因爲k'< k）=>與價值（P'）<值（Next（P））的事實形成對比。因爲值（P'）>值（P），但我們知道，直到k'P和P'是相同的，所以，所以存在k''> k'，使得P [k'']與[Next]的定義形成對比（對於k是最右邊的事實，P [k] <P [k'] 1]）。這是因爲我們可以在鏈P [k'] P [k'+ 1] .. P [k「]中找到兩個鄰居X，Y，例如X < Y.

• k'= k'：if下一個（P）[K'] < P'[K]我們將得到那個值（P'）>值（下一個（P）），這是不正確的。如果P'[k] = Next（P）[k]，因爲k是最右邊的並且因爲值（P'）= value（Next（P）），所以我們得到P'= Next（P），它不能因爲value（Next（P））> value（P'），所以爲true。如果P '[k]的下一個<（P [k]的）它不能是類似於選項2.

因此，我們得到這樣的P' 是不可能=>下一步（P）爲我們想要P的下一個排列。

示例： P =「DFEBCA」 下一個（P）=「DFECBA」。

因此k = 4，因爲4是最右邊的索引，例如P [i] < P [i + 1]。 （P）< value（Next（P）） 您不會找到。

Answer 3

有用的鏈接on permutations - 算法在那裏解釋。

我也很難理解邏輯，所以這裏是我的高層次概述。

基本上元件你重排列的序列（字符/數字。）可分爲兩個部分 - 的前綴和後綴。後綴是從正確的「第一個字符」的一切。

算法「增加」前綴通過交換「的第二字符」（這是在後綴並且是越小交換元件的）與「第一字符」（這是最右邊的元件在前綴並且是更大的之一）。選擇「第二個字符」和「第一個字符」以表示前綴中可能的最小增量。

通過在前綴中儘可能小的增加（通過交換操作完成），您可以說將序列從增加（第一個置換）轉換爲減少（最後一個置換），可以得到這些元素的所有可能序列。

爲什麼在交換後對後綴進行排序？爲了使後綴「儘可能小」，所以我們不必在接下來的幾次迭代中增加「當前」前綴（通過當前前綴我指的是算法的這一步中的前綴）

Answer 4

要打印下一個我們需要按照下面所述的算法的詞典術語： - >

1. 計算單詞的長度並使您的指針指向該單詞的最後一個字符和最後一個字符。如果倒數第二個字符小於最後一個字符，則交換兩個字符。這是所需的答案。
2. 如果第一個情況沒有發生，那麼讓第二個最後的指針（比如說i）減1並搜索字符，該字符大於右邊的子字符串中最小的字符。如果找到這樣的字符，則用找到的天花板字符（右邊一個）替換位置字符。
3. 現在，最後對指針i右邊的子串進行排序，否則重複第二步。