std::next_permutation 演算法如何找到序列的下一個字典順序更大的排列？

std::next_permutation 實作說明

std::next_permutation 演算法計算給定序列的下一個字典順序更大的排列。理解其實現對於理解其行為至關重要。

演算法概述

演算法從右到左迭代序列，搜尋最左邊的「上升部分」（即，小於其後繼的元素）。如果沒有找到升序，則表示序列是降序排列，在這種情況下，它將反轉序列以獲得最小排列。

否則，演算法會繼續尋找序列中右側的最小元素上升器（稱為「k」）。然後該元素與上行元素交換。最後，將升序右側的元素反轉以保持降序。

變數角色

• i: 指向目前正在檢查的元素。
• j: 指向緊鄰 i 之前的元素。
• k: 指向序列中最小的元素當 i 是上升時，位於 i 的右側。

循環流

循環迭代，直到 i 到達序列的開頭（開始）。在每次迭代中：

1. 如果 i 不是上行元素，則遞減 i 和 j。
2. 如果 i 是上行元素，則尋找 i 右側的最小元素（k )，與 i 交換，並將 i 右側的所有內容反轉。

範例

考慮序列{1, 2, 4, 3} .

• 迭代1:>迭代1: 🎜> i 最初位於3。 j 位於 2。因為 3 4 (i
• 迭代 2： k 被發現為 2。3 與 2 交換。 {1, 3, 4, 2} 。 3 右邊的元素（4 和 2）顛倒過來。 {1, 3, 2, 4}.
• 迭代 3： i 遞減，j 遞減。 i 現在為 2。 j 為 1. 2
• 迭代 4： k 被發現為 1。2 與 1 交換。 {1, 2, 4, 3}。 2 右邊的元素（4 和 3）顛倒過來。 {1, 2, 3, 4}.
• 迭代 5： i 遞減，j 遞減。 i 現在為 1。 j 位於序列的開頭。由於不再有上升部分，因此順序相反。 {4, 3, 2, 1}.

以上是std::next_permutation 演算法如何找到序列的下一個字典順序更大的排列？的詳細內容。更多資訊請關注PHP中文網其他相關文章！