首頁 > 後端開發 > C++ > std::next_permutation 如何找出下一個字典順序更大的排列?

std::next_permutation 如何找出下一個字典順序更大的排列?

Susan Sarandon
發布: 2024-11-08 00:44:02
原創
252 人瀏覽過

How Does std::next_permutation Find the Next Lexicographically Greater Permutation?

std::next_permutation 如何運作

std::next_permutation 是C 標準範本庫(STL) 中的函數,用於對序列重新排序進入下一個字典順序更大的排列。為了理解其實現,將序列視覺化為一個數字是很有幫助的,其中每個元素代表一個數字。

核心邏輯

演算法依照下列原則運作:

  • 找出樞軸: 從序列結尾開始,它找到小於其右側元素(j) 的第一個元素(i)。這表示 i 右邊的數字依降序排列。
  • 交換與反轉: 一旦找到 i,它就會從最後開始找出第一個元素 (k),大於 i。該元素與 i 交換,將其放在前面。然後將 j 右側的剩餘元素(從 j 到 end)反轉。
  • 增加樞軸: 如果找到樞軸(i 不是開頭),則重複此過程透過遞減 i 和 j。
  • 反轉並退出:如果找不到主元(i 為開頭),則反轉序列,函數傳回false,表示不再排列

程式碼中的變數

  • i: 代表最左邊的主元元素。
  • j: 表示 i 右邊小於 i 的元素。
  • k: 表示從右邊開始大於 i 的元素,將與 i 交換。

考慮序列:1, 3, 2, 4。

  • 找出樞軸: i 最初設定為 4,但由於 4 大於或等於 2,所以我們移動到 i = 2。由於 2 小於 4,所以 i 是樞軸。
  • 交換與反轉: j 設定為 3,k 設定為 1,即右側第一個大於 2 的元素。 1 與 2 交換,得到 1, 2, 3 , 4. 從 j 到末尾 (2, 3, 4) 的剩餘元素被反轉,得到 1, 2, 4, 3。
  • 增加主元: i 減少到 1 (j 已設定為 2)。由於 1 小於 2,因此重複此過程。
  • 找樞軸: i 遞減到第一個元素(開始),表示找不到樞軸。
  • 反轉並退出:序列反轉其原始狀態 1, 2, 3, 4 且函數傳回 false,表示不再可能進行排列。

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

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板