生成输入序列的序列

当测试代码需要处理参数顺序不重要的输入序列时，有必要测试它是否对所有可能的输入产生相同的输出。当你自己实现了一个排序算法时，就要写这样的测试代码来确定自己的实现是否正确。

std::next_permutation在任何时候都能帮我们将序列进行打乱。我们在可修改的范围中可以调用它，其会将以字典序进行置换。

How to do it…

本节，我们将从标准输入中读取多个字符串，然后使用std::next_permutation生成已排序的序列，并且打印这个序列：

  1. 首先，包含必要的头文件，并声明所使用的命名空间。

    1. #include <iostream>
    2. #include <vector>
    3. #include <string>
    4. #include <iterator>
    5. #include <algorithm>
    7. using namespace std;

  2. 使用标准数组对vector进行初始化，接下来对vector进行排序：

    1. int main()
    2. {
    3.     vector<string> v {istream_iterator<string>{cin}, {}};
    4.     sort(begin(v), end(v));

  3. 现在来打印vector中的内容。随后，调用std::next_permutation，其会打乱已经排序的vector，再对其进行打印。直到next_permutation返回false时，代表next_permutation完成了其操作，循环结束：

    1.     do {
    2.         copy(begin(v), end(v),
    3.             ostream_iterator<string>{cout, ", "});
    4.         cout << '\n';
    5.     } while (next_permutation(begin(v), end(v)));
    6. }

  4. 编译运行这个程序，会有如下的打印：

    1. $ echo "a b c" | ./input_permutations
    2. a, b, c,
    3. a, c, b,
    4. b, a, c,
    5. b, c, a,
    6. c, a, b,
    7. c, b, a,

How it works…

std::next_permutation算法使用起来有点奇怪。因为这个函数接受一组开始/结束迭代器，当其找到下一个置换时返回true；否则，返回false。不过“下一个置换”又是什么意思呢？

当std::next_permutation算法找到元素中的下一个字典序时，其会以如下方式工作：

  1. 通过v[i - 1] < v[i]的方式找到最大索引i。如果这个最大索引不存在，那么返回false。
  2. 再找到最大所以j，这里j需要大于等于i，并且v[j] > v[i - 1]。
  3. 将位于索引位置j和i - 1上的值进行交换。
  4. 将从i到范围末尾的元素进行反向。
  5. 返回true。

每次单独的置换顺序，都会在同一个序列中呈现。为了看到所有置换的可能，我们先对数组进行了排序。如果我们输入“c b a”到算法中，算法会立即终止，因为每个元素都以反字典序排列。