next_permutation和prev_permutation函数使用的是字典序算法，即通过比较相邻的排列，从而找到下一个或上一个排列。具体实现方式为，从序列的最后一个元素开始遍历，找到第一个满足a[i]<a[i+1]的元素a[i]，然后在i的右边找到最小的元素a[j]，使得a[j]>a[i]，将a[i]和a[j]互换位置，最后将i右边的元素按升序排列，从而得到下一个排列。prev_permutation函数实现方式类似，只是将上述步骤中的<和>反转即可。

该算法用于对区间元素进行组合排列，选择一个字典顺序更大或更小的排列。

#include <iostream>
#include <algorithm>

using namespace std;

void MyPrint(int x) { cout << x << " "; }

// 排序函数
template <class BidirectionalIter>
void nextPermu_sort(BidirectionalIter first, BidirectionalIter last)
{
  // 利用较大的组合返回true
  while (next_permutation(first, last)){}
}

int main(int argc, char* argv[])
{
  int iArray[] = { 3, 5, 8, 1, 8, 9, 3, 2, 1, 9 };
  const int len = sizeof(iArray) / sizeof(int);

  // 下一排列组合
  next_permutation(iArray, iArray + len);
  for_each(iArray, iArray + len, MyPrint);
  cout << endl;

  // 上一排列组合
  prev_permutation(iArray, iArray + len);
  for_each(iArray, iArray + len, MyPrint);

  system("pause");
  return 0;
}

9.10 容器元素求和算法

accumulate、inner_product和partial_sum 算法函数，分别用于计算序列中的累加和、内积和和部分和序列。它们的用法如下：

template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);

template<class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);

template<class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);

其中，first、last、first1、last1、first2是输入迭代器，表示待计算的序列范围；init是计算的初始值，result是输出迭代器，表示计算结果的位置。accumulate函数返回序列中元素的累加和，inner_product函数返回序列的内积和，partial_sum函数返回序列的部分和序列。这些函数将计算结果复制到由result指定的迭代器范围内，并返回一个指向输出序列尾后位置的迭代器。

需要说明的是，accumulate和inner_product函数可以接受一个自定义的二元操作符（比如加法、乘法等），从而实现各种自定义的累加和和内积和的计算。partial_sum函数不需要自定义操作符，固定使用加法运算。

accumulate、inner_product和partial_sum函数使用的都是迭代算法，在遍历序列时进行累加和、内积和和部分和的计算。具体实现方式为，遍历序列中的元素，根据特定的操作符将每个元素进行累加、相乘或相加，从而得到总体的累加和、内积和或部分和序列。

#include <iostream>
#include <numeric>
#include <algorithm>

using namespace std;

void MyPrint(int x) { cout << x << " "; }

int multiply(int x, int y) { return x*y; }

int main(int argc, char* argv[])
{
  // 求数组元素相加之和
  int iArray[5] = {1,2,3,4,5};
  cout << accumulate(iArray, iArray + 5, 0) << endl;

  // 求数组元素的内积
  int iArray1[3] = { 2, 5, 4 };
  int iArray2[3] = { 10, 6, 5 };
  cout << inner_product(iArray1, iArray1 + 3, iArray2, 0) << endl;

  // 部分元素求和
  int iArray3[5] = { 1, 2, 3, 4, 5 };
  int result[5];

  partial_sum(iArray3, iArray3 + 5, result);
  for_each(iArray3, iArray3 + 5, MyPrint);
  cout << endl;

  // 求阶乘
  int result1[5];
  partial_sum(iArray3, iArray3 + 5, result1,multiply);
  for_each(result1, result1 + 5, MyPrint);

  system("pause");
  return 0;
}

本文作者： 王瑞
本文链接： https://www.lyshark.com/post/bba79f2e.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！