4

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

最困扰我的部分是我不明白为什么我们必须写 sort(sides,ides+3) 和 next_permutation(sides,ides+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;
}
4

3 回答 3

2

欧几里得几何告诉我们：
两条边之和总是大于另一条边

让我们看一个三角形ABC。
AB = 3
BC = 5
AC = 4

std::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/

于 2013-08-01T19:26:20.627 回答
2

std::next_permutation 文档

将范围转换为下一个排列 将范围 [first,last) 中的元素重新排列为下一个字典顺序更大的排列。

所以除非你开始排序，否则你不会经历所有排列

所以如果你从

1,2,3

最后的排列是

3,2,1

如果你从

3,1,2

只会再找到一个排列，而不是全部

于 2013-08-01T19:31:12.560 回答
1

看看std::next_permuntation不排序时的结果：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>

enum class sort { no, yes };

void show_permutations(std::string s, sort option) {
  if (sort::yes == option) {
    std::sort(std::begin(s), std::end(s));
  }

  do {
    std::cout << s << '\n';
  } while (std::next_permutation(std::begin(s), std::end(s)));
}

int main() {
  show_permutations("3412", sort::yes);

  std::cout << "Now without sorting...\n";

  show_permutations("3412", sort::no);
}

检查输出，看看你是否注意到任何有趣的事情：

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
Now without sorting...
3412
3421
4123
4132
4213
4231
4312
4321

没有排序创建的序列与使用排序创建的序列的最末端相同。这意味着输入顺序的重要性是什么？

如果将排序代码放入循环中，您认为会发生什么？

void show_permutations(std::string s, sort option) {
  do {

    if (sort::yes == option) {
      std::sort(std::begin(s), std::end(s));
    }

    std::cout << s << '\n';
  } while (std::next_permutation(std::begin(s), std::end(s)));
}

请注意，您的程序对循环内的三角形边next_permutation进行排序，类似于此代码在循环内对输入字符串进行排序。

于 2013-08-01T20:07:47.890 回答