std::next_permutation 实现说明

std::next_permutation 算法计算给定序列的下一个字典顺序更大的排列。理解其实现对于理解其行为至关重要。

算法概述

该算法从右到左迭代序列，搜索最左边的“上升部分”（即，小于其后继的元素）。如果没有找到上升符，则意味着序列是降序排列，在这种情况下，它将反转序列以获得最小排列。

否则，算法继续寻找序列中向右的最小元素上升器（称为“k”）。然后该元素与上行元素交换。最后，将上升部分右侧的元素反转以保持降序。

变量角色

• i: 指向
• j: 指向 i 之前的元素。
• k: 指向序列中最小的元素

循环流

循环迭代，直到 i 到达序列的开头（开始）。在每次迭代中：

1. 如果 i 不是上行元素，则递减 i 和 j。
2. 如果 i 是上行元素，则查找 i 右侧的最小元素 (k )，将其与 i 交换，并将 i 右侧的所有内容反转。

示例

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

• 迭代 1: i 最初位于 3。j 位于 2。由于 3
• 迭代 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}.