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: 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中文网其他相关文章！