时间戳

首页 > 解决方案 > 为什么我不能使用 std::next_permutation 生成所有排列？

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

问题描述

我正在尝试使用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 中的代码。它也显示在下面。

#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

标签： c++stlc++14permutation

解决方案

从参考：

将范围 [first, last) 排列到下一个排列中，其中所有排列的集合按字典顺序相对于 operator< 或 comp 排序。

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

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

推荐阅读