c++ - 使用 std::sort 和 std::next_permutation

Question

我编写了以下代码并且运行良好。我只是无法理解它为什么起作用。更具体地说，为什么我们必须先对数组进行排序才能使用 std::next_permutation，它不能从任何配置开始吗？

最让我困扰的部分是我不明白为什么我们必须写sort(sides, sides+3) 和 next_permutation(sides, sides+3) 为什么是“+3”!因为我在数组中有三个元素？如果我使用任意数量的元素怎么办？

bool valid(int sides[], ofstream &outfile)
{
  int i = 0;
  for(; i < 3; i++) {
    if(sides[i] <= 0) {
      outfile << "This is not a valid triangle because it\n "
              << "contains negative sides or contains a\n"
              << "side length of 0\n\n";
      return false;
    }
  }

  do{
    std::sort(sides,sides+3);
    if(sides[0] + sides[1] > sides[2])
      ;
    else{
      outfile << "This is not a valid triangle because "
              << sides[0] << " + " << sides[1]
              << " is not greater than " << sides[2];
      return false;
    }
  }while(std::next_permutation(sides,sides+3));

  return true;
}

Answer 1

欧氏几何告诉我们:
两条边的和总是大于剩下的边

Lets take a triangle ABC.
AB = 3
BC = 5
AC = 4

std::sort 将边按升序排序。这样数组将首先包含较短的边。

after sort
side[0] = AB = 3
side[1] = AC = 4
side[2] = BC = 5

std::next_permutation 返回边的下一个可能组合。例如:

AC = 3
BC = 5
AB = 4

一个简单的例子:

#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";

  while ( std::next_permutation(myints,myints+3) )
  {
    std::cout << myints[0] << ' ' << myints[1];
    std::cout << ' ' << myints[2] << '\n';
  }

  std::cout << "After loop: " << myints[0] << ' ';
  std::cout << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

进一步阅读:http://www.cplusplus.com/reference/algorithm/next_permutation/