Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1704299
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-09-10 22:32:50

当第一眼看见这个函数名字的时候,还以为是求卡特兰数,结果不是,是发现排列组合规律的一个函数。

已知:容器当中有一系列的元素

求:当容器当中的元素满足一定的比较关系时,当前容器内的元素对应的排列组合的下一个排列组合

例如:当前序列为{b, c, a}, 其共有三个元素,有3!个排列组合即:

a, b, c;

a, c, b;

b, a, c;

b, c, a;

c, a, b;

c, b, a;

那么当前序列的next_permutation为:{c, a, b}, prev_permutation为:{}b, a, c},

在这个过程当中简而言之:从最尾端开始向前寻找两个相邻元素,找到第一对满足后面的元素(b)比前面的元素(a)的值大;下一步在较小值(a)之后,从尾端开始寻找到第一个大于a的值(c),将c与a交换,之后再将b之后的元素颠倒排序,代码如下:



点击(此处)折叠或打开

  1. template <class BidirectionalIterator>
  2. bool next_permutation(BidirectionalIterator first,
  3.                       BidirectionalIterator last) {
  4.   if (first == last) return false;
  5.   BidirectionalIterator i = first;
  6.   ++i;
  7.   if (i == last) return false;
  8.   i = last;
  9.   --i;

  10.   for(;;) {
  11.     BidirectionalIterator ii = i;
  12.     --i;
  13.     if (*i < *ii) {
  14.       BidirectionalIterator j = last;
  15.       while (!(*i < *--j));
  16.       iter_swap(i, j);
  17.       reverse(ii, last);
  18.       return true;
  19.     }
  20.     if (i == first) {
  21.       reverse(first, last);
  22.       return false;
  23.     }
  24.   }
  25. }

prev_permutation的思路跟next_permutation的思路差不多,就是查找条件不一样,这里直接上代码了哈~



点击(此处)折叠或打开

  1. template <class BidirectionalIterator>
  2. bool prev_permutation(BidirectionalIterator first,
  3.                       BidirectionalIterator last) {
  4.   if (first == last) return false;
  5.   BidirectionalIterator i = first;
  6.   ++i;
  7.   if (i == last) return false;
  8.   i = last;
  9.   --i;

  10.   for(;;) {
  11.     BidirectionalIterator ii = i;
  12.     --i;
  13.     if (*ii < *i) {
  14.       BidirectionalIterator j = last;
  15.       while (!(*--j < *i));
  16.       iter_swap(i, j);
  17.       reverse(ii, last);
  18.       return true;
  19.     }
  20.     if (i == first) {
  21.       reverse(first, last);
  22.       return false;
  23.     }
  24.   }
  25. }

Stl就先讲到这里吧~~

阅读(2085) | 评论(0) | 转发(0) |
0

上一篇:stl当中的power函数

下一篇:回炉线性代数

给主人留下些什么吧!~~