一、前言

本文使用C++来实现全排列算法。

说明:本文代码需支持C++标准编译器编译,以及可选单元测试工具googletest

项目地址:algorithm

二、函数声明

// 下一个字典序排列
// [first, last) 左闭右开区间,默认比较函数使用 std::less
// 若存在排列,返回 true
// 若不存在排列,返回 false,并且排列为第一个字典序排列(即有序)
template<class It, class Compare = std::less<typename std::iterator_traits<It>::value_type>>
constexpr bool NextPermutation(It first, It last, Compare Cmp = Compare());
// 上一个字典序排列
// [first, last) 左闭右开区间,默认比较函数使用 std::less
template<class It, class Compare = std::less<typename std::iterator_traits<It>::value_type>>
constexpr bool PrevPermutation(It first, It last, Compare Cmp = Compare());

三、函数实现

3.1 NextPermutation

NextPremutation以字典序顺序输出数组。

数组{'a','b','c'},其字典序为abc < acb < bac < bca < cab < cba

数组{'b','c','a'},其字典序为bca < cab < cba

算法步骤如下:

一、若含有一个及以下元素直接返回false

二、在数组元素由后向前查找,查找到第一对具有小于关系的元素位置。

三、若不存在具有小于关系元素(所有元素按降序排序),逆序后返回false

四、若存在i < ii,则对于i之后的元素是降序排列。

五、在降序序列中(i之后元素),由后向前查找到满足j > i的元素j的最小值。

六、交换j和元素i,交换后后部分仍满足降序,逆序后为升序,算法结束。

template<class It, class Compare = std::less<typename std::iterator_traits<It>::value_type>>
constexpr bool NextPermutation(It first, It last, Compare Cmp = Compare()) {
  // 存在一个或以下元素个数,直接返回 false
  if(first == last) { return false; }
  It i = last;
  if(first == --i) { return false; }
  while(true) {
    It ii = i;
    // 查找第一个满足小于关系的元素对
    if(Cmp(*--i, *ii)) {
      // 逆序查找元素,使 j > i
      It j = last;
      while(!Cmp(*i, *--j)) {}
      // 交换后,使后部分降序序列为升序
      std::iter_swap(i, j);
      std::reverse(ii, last);
      return true;
    }
    // 不存在满足小于关系元素对,即元素降序排列,返回升序排列
    if(i == first) {
      std::reverse(first, last);
      return false;
    }
  }
}

3.2 PrevPermutation

PrevPermutationNextPermutation一致,修改其比较方式即可。

template<class It, class Compare = std::less<typename std::iterator_traits<It>::value_type>>
constexpr bool PrevPermutation(It first, It last, Compare Cmp = Compare()) {
  if(first == last) { return false; }
  It i = last;
  if(first == --i) { return false; }
  while(true) {
    It ii = i;
    if(Cmp(*ii, *--i)) {
      It j = last;
      while(!Cmp(*--j, *i)) {}
      std::iter_swap(i, j);
      std::reverse(ii, last);
      return true;
    }
    if(i == first) {
      std::reverse(first, last);
      return false;
    }
  }
}

四、单元测试

  • 用例一:有序升序数组全排列验证next_permutation
  • 用例二:随机数组全排列验证next_permutation
  • 用例三:有序降序数组全排列验证prev_permutation
  • 用例四:随机数组全排列验证prev_permutation

测试结果:

[==========] Running 4 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 4 tests from PermutationTest
[ RUN      ] PermutationTest.next_permutation
[       OK ] PermutationTest.next_permutation (449 ms)
[ RUN      ] PermutationTest.next_permutation_random
[       OK ] PermutationTest.next_permutation_random (266 ms)
[ RUN      ] PermutationTest.prev_permutation
[       OK ] PermutationTest.prev_permutation (4713 ms)
[ RUN      ] PermutationTest.prev_permutation_random
[       OK ] PermutationTest.prev_permutation_random (1178 ms)
[----------] 4 tests from PermutationTest (6606 ms total)

[----------] Global test environment tear-down
[==========] 4 tests from 1 test suite ran. (6606 ms total)
[  PASSED  ] 4 tests.

五、相关练习

Last modification:June 19th, 2020 at 06:58 pm