为什么我不能用 std::next_permutation 生成所有排列？

Question

我正在尝试使用 C++14 STL 中的 std::next_permutation 获取二进制值的所有排列（在本例中，二进制值由整数 0 和 1 表示）。

但是，我确实认为我在这个方法中发现了一个错误。
如果向量在其端上有一个或多个零，那么一个不能获得所有排列矢量。

例如，让我们考虑向量 std::vector<int> a = {1,0,0}。 std::next_permutation 找到的唯一排列是 {(1 0 0)}，而存在三种可能的排列 {(1 0 0), (0 1 0), (0 0 1)}.

这是一个错误吗？如果有，我可以在哪里举报？

您可以使用 C++ shell here 访问我的代码。它也显示在下面。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {

  std::vector<int> a = {1,0,0,0};
  std::vector<int> b = {0,0,0,1};

  std::cout << "Permutations of a" << std::endl;
  do {
    for (int i = 0; i < a.size(); i++) {
      std::cout << a[i];
    }
  std::cout << std::endl;
  } while (std::next_permutation(a.begin(), a.end()));
  
  
  std::cout << std::endl << "Permutations of b" << std::endl;
  
  do {
    for (int i = 0; i < b.size(); i++) {
      std::cout << b[i];
    }
    std::cout << std::endl;
  } while (std::next_permutation(b.begin(), b.end()));
  exit(0);
}

输出：

Permutations of a
1000

Permutations of b
0001
0010
0100
1000

Answer 1

来自reference：

Permutes the range [first, last) into the next permutation, where the set of all permutations is ordered lexicographically with respect to operator< or comp.

因此遍历排列只会为您提供从初始范围开始按字典序递增的序列。

请注意，参考页底部的示例在初始范围上执行 std::sort 以生成 all 排列。

Answer 2

来自 C++20 标准 [alg.permutation.generators]:

Effects: Takes a sequence defined by the range [first, last) and transforms it into the next permutation. The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to comp and proj. If no such permutation exists, transforms the sequence into the first permutation; that is, the ascendingly-sorted one.

你的a已经在最后一个排列了，所以函数returnsfalse。就像b达到相同状态时一样。

为什么我不能用 std::next_permutation 生成所有排列？

Why can't I generate all permutations with std::next_permutation?

c++

stl

permutation

c++14