高效编码帮助

Question

我目前正在用C++编写代码，以查找6个整数的所有可能的排列，并存储最佳排列(即，其总和最接近给定值的排列)。

我正在尝试写这段代码尽可能有效，并将感谢任何建议或例子。

我考虑将整数存储在数组中，并使用循环中的指针执行排列。这是一种好的方法吗？

Answer 1

他们已经为你想好了：

#include <algorithm>

int ra[6] = { 1, 2, 3, 4, 5, 6 };

do {
    // whatever
} while (std::next_permutation(ra, ra+6));

注意，元素必须以递增的顺序开始(通过operator<进行比较)，否则循环将在您看到每个排列之前终止。详情请参见http://en.cppreference.com/w/cpp/algorithm/next_permutation。

它可能不会给出最快的运行时，因为在每一步它都必须检查数组以确定要更改什么。但在程序员的努力下，它肯定是最有效的，而且如果不知道编译器和平台，无论如何也不可能对嵌套循环方法进行微优化。

Answer 2

看看这篇优秀的文章@ Coding the Wheel：Exhaustively Enumerating Combinations and Permutations in Code。它有完整的代码，并且是由一个SO'r写的，它应该足以让你走上正确的道路。

Answer 3

假设重复的数字不是问题，那么有n个！N个整数的累加(一次取n个)。因此，无论您做什么，您的算法都将具有阶乘时间行为(O (n^n) )。

换句话说，当n变大时，它将是慢的。抱歉的。

实际上，在permutation wikipedia页面上有一些算法可以做到这一点。