什么是 C++ 中使用最广泛的现有库，可以提供 n 个元素中 k 个元素的所有组合和排列？
我不是在问算法，而是在问现有的库或方法。
谢谢。
问问题
24803 次
5 回答
39
我决定在这里测试 dman 和 Charles Bailey 的解决方案。我将它们分别称为解决方案 A 和 B。我的测试是一次访问vector<int>size = 100, 5 的每个组合。这是测试代码：
测试代码
struct F
{
unsigned long long count_;
F() : count_(0) {}
bool operator()(std::vector<int>::iterator, std::vector<int>::iterator)
{++count_; return false;}
};
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double> sec;
typedef std::chrono::duration<double, std::nano> ns;
int n = 100;
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 0);
std::vector<int>::iterator r = v.begin() + 5;
F f;
Clock::time_point t0 = Clock::now();
do
{
f(v.begin(), r);
} while (next_combination(v.begin(), r, v.end()));
Clock::time_point t1 = Clock::now();
sec s0 = t1 - t0;
ns pvt0 = s0 / f.count_;
std::cout << "N = " << v.size() << ", r = " << r-v.begin()
<< ", visits = " << f.count_ << '\n'
<< "\tnext_combination total = " << s0.count() << " seconds\n"
<< "\tnext_combination per visit = " << pvt0.count() << " ns";
}
所有代码都是在 2.8 GHz Intel Core i5 上使用 clang++ -O3 编译的。
解决方案 A
解决方案 A 导致无限循环。即使我n做得很小，这个程序也永远不会完成。后来因为这个原因被否决了。
解决方案 B
这是一个编辑。解决方案 B 在编写此答案的过程中发生了变化。起初它给出了错误的答案，并且由于非常及时的更新，它现在给出了正确的答案。它打印出来：
N = 100, r = 5, visits = 75287520
next_combination total = 4519.84 seconds
next_combination per visit = 60034.3 ns
解决方案 C
接下来我尝试了N2639的解决方案，它看起来与解决方案 A 非常相似，但工作正常。我将此解决方案称为 C 并打印出：
N = 100, r = 5, visits = 75287520
next_combination total = 6.42602 seconds
next_combination per visit = 85.3531 ns
解决方案 C 比解决方案 B 快 703 倍。
解决方案 D
最后在这里找到了一个解决方案D。这个解决方案有不同的签名/风格，被称为for_each_combination，使用起来很像std::for_each。上面的驱动程序代码在定时器调用之间发生变化，如下所示：
Clock::time_point t0 = Clock::now();
f = for_each_combination(v.begin(), r, v.end(), f);
Clock::time_point t1 = Clock::now();
解决方案 D 打印出：
N = 100, r = 5, visits = 75287520
for_each_combination = 0.498979 seconds
for_each_combination per visit = 6.62765 ns
解决方案 D 比解决方案 C 快 12.9 倍，比解决方案 B 快 9000 多倍。
我认为这是一个相对较小的问题：只有 7500 万次访问。随着访问次数增加到数十亿，这些算法之间的性能差异继续扩大。解决方案 B 已经很笨拙了。解决方案 C 最终变得笨拙。解决方案 D 是访问我所知道的所有组合的性能最高的算法。
显示解决方案 D的链接还包含其他几种算法，用于枚举和访问具有各种属性（循环、可逆等）的排列。这些算法中的每一个都是以性能作为目标之一而设计的。请注意，这些算法都不要求初始序列按排序顺序排列。元素甚至不需要LessThanComparable。
于 2011-03-13T00:08:38.577 回答
20
组合：来自Mark Nelson关于同一主题的文章，我们有next_combination排列：来自 STL，我们有std::next_permutation
template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
if ((first == last) || (first == k) || (last == k))
return false;
Iterator itr1 = first;
Iterator itr2 = last;
++itr1;
if (last == itr1)
return false;
itr1 = last;
--itr1;
itr1 = k;
--itr2;
while (first != itr1)
{
if (*--itr1 < *itr2)
{
Iterator j = k;
while (!(*itr1 < *j)) ++j;
std::iter_swap(itr1,j);
++itr1;
++j;
itr2 = k;
std::rotate(itr1,j,last);
while (last != j)
{
++j;
++itr2;
}
std::rotate(k,itr2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
于 2010-02-06T04:30:23.490 回答
17
这个答案提供了一个最小的实施工作解决方案。如果您想检索大输入范围的组合，它可能没有可接受的性能。
标准库具有std::next_permutation并且您可以轻松地next_k_permutation从它构建一个并next_combination从中构建一个。
template<class RandIt, class Compare>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last, Compare comp)
{
std::sort(mid, last, std::tr1::bind(comp, std::tr1::placeholders::_2
, std::tr1::placeholders::_1));
return std::next_permutation(first, last, comp);
}
如果您没有，tr1::bind或者boost::bind您需要构建一个将参数交换到给定比较的函数对象。当然，如果你只对一个std::less变体感兴趣，next_combination那么你可以std::greater直接使用：
template<class RandIt>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits<RandIt>::value_type value_type;
std::sort(mid, last, std::greater< value_type >());
return std::next_permutation(first, last);
}
这是一个相对安全的版本next_combination。如果您可以保证范围[mid, last)与调用后的顺序一样，next_combination那么您可以使用更简单的：
template<class BiDiIt, class Compare>
bool next_k_permutation(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
std::reverse(mid, last);
return std::next_permutation(first, last, comp);
}
这也适用于双向迭代器以及随机访问迭代器。
要输出组合而不是 k 排列，我们必须确保每个组合只输出一次，因此只有当它是按顺序排列的 k 排列时，我们才会返回一个组合。
template<class BiDiIt, class Compare>
bool next_combination(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
bool result;
do
{
result = next_k_permutation(first, mid, last, comp);
} while (std::adjacent_find( first, mid,
std::tr1::bind(comp, std::tr1::placeholders::_2
, std::tr1::placeholders::_1) )
!= mid );
return result;
}
替代方法是使用反向迭代器而不是参数交换bind调用，或者std::greater如果std::less正在使用比较，则显式使用。
于 2010-04-11T11:25:32.867 回答
2
@查尔斯贝利以上：
我可能是错的，但我认为上面的前两个算法不会删除 first 和 mid 之间的重复项？也许我不确定如何使用它。
4 选择 2 示例：
12 34
12 43（排序后）
13 24（next_permutation 后）
13 42（排序后）
14 23（next_permutation 后）
14 32（排序后）
21 34（next_permutation 后）
所以我在返回之前添加了一个检查以查看斜体的值是否正确，但绝对不会想到你写的部分（非常优雅！谢谢！）。
没有完全测试，只是粗略的测试..
template
bool next_combination(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits< RandIt >::value_type value_type;
std::sort(mid, last, std::greater< value_type >() );
while(std::next_permutation(first, last)){
if(std::adjacent_find(first, mid, std::greater< value_type >() ) == mid){
return true;
}
std::sort(mid, last, std::greater< value_type >() );
return false;
}
于 2011-01-06T01:58:55.347 回答
0
也许它已经在之前的答案中说明了，但是在这里我找不到关于参数类型的完整通用方法，而且我也没有在 Boost 之外的现有库例程中找到它。这是我在测试用例构建过程中需要的一种通用方法，用于具有广泛各种参数变化的场景。也许它对你也有帮助，至少对于类似的情况。（可用于有疑问的微小变化的排列和组合）
#include <vector>
#include <memory>
class SingleParameterToVaryBase
{
public:
virtual bool varyNext() = 0;
virtual void reset() = 0;
};
template <typename _DataType, typename _ParamVariationContType>
class SingleParameterToVary : public SingleParameterToVaryBase
{
public:
SingleParameterToVary(
_DataType& param,
const _ParamVariationContType& valuesToVary) :
mParameter(param)
, mVariations(valuesToVary)
{
if (mVariations.empty())
throw std::logic_error("Empty variation container for parameter");
reset();
}
// Step to next parameter value, return false if end of value vector is reached
virtual bool varyNext() override
{
++mCurrentIt;
const bool finished = mCurrentIt == mVariations.cend();
if (finished)
{
return false;
}
else
{
mParameter = *mCurrentIt;
return true;
}
}
virtual void reset() override
{
mCurrentIt = mVariations.cbegin();
mParameter = *mCurrentIt;
}
private:
typedef typename _ParamVariationContType::const_iterator ConstIteratorType;
// Iterator to the actual values this parameter can yield
ConstIteratorType mCurrentIt;
_ParamVariationContType mVariations;
// Reference to the parameter itself
_DataType& mParameter;
};
class GenericParameterVariator
{
public:
GenericParameterVariator() : mFinished(false)
{
reset();
}
template <typename _ParameterType, typename _ParameterVariationsType>
void registerParameterToVary(
_ParameterType& param,
const _ParameterVariationsType& paramVariations)
{
mParametersToVary.push_back(
std::make_unique<SingleParameterToVary<_ParameterType, _ParameterVariationsType>>(
param, paramVariations));
}
const bool isFinished() const { return mFinished; }
void reset()
{
mFinished = false;
mNumTotalCombinationsVisited = 0;
for (const auto& upParameter : mParametersToVary)
upParameter->reset();
}
// Step into next state if possible
bool createNextParameterPermutation()
{
if (mFinished || mParametersToVary.empty())
return false;
auto itPToVary = mParametersToVary.begin();
while (itPToVary != mParametersToVary.end())
{
const auto& upParameter = *itPToVary;
// If we are the very first configuration at all, do not vary.
const bool variedSomething = mNumTotalCombinationsVisited == 0 ? true : upParameter->varyNext();
++mNumTotalCombinationsVisited;
if (!variedSomething)
{
// If we were not able to vary the last parameter in our list, we are finished.
if (std::next(itPToVary) == mParametersToVary.end())
{
mFinished = true;
return false;
}
++itPToVary;
continue;
}
else
{
if (itPToVary != mParametersToVary.begin())
{
// Reset all parameters before this one
auto itBackwd = itPToVary;
do
{
--itBackwd;
(*itBackwd)->reset();
} while (itBackwd != mParametersToVary.begin());
}
return true;
}
}
return true;
}
private:
// Linearized parameter set
std::vector<std::unique_ptr<SingleParameterToVaryBase>> mParametersToVary;
bool mFinished;
size_t mNumTotalCombinationsVisited;
};
可能的用法：
GenericParameterVariator paramVariator;
size_t param1;
int param2;
char param3;
paramVariator.registerParameterToVary(param1, std::vector<size_t>{ 1, 2 });
paramVariator.registerParameterToVary(param2, std::vector<int>{ -1, -2 });
paramVariator.registerParameterToVary(param3, std::vector<char>{ 'a', 'b' });
std::vector<std::tuple<size_t, int, char>> visitedCombinations;
while (paramVariator.createNextParameterPermutation())
visitedCombinations.push_back(std::make_tuple(param1, param2, param3));
生成：
(1, -1, 'a')
(2, -1, 'a')
(1, -2, 'a')
(2, -2, 'a')
(1, -1, 'b')
(2, -1, 'b')
(1, -2, 'b')
(2, -2, 'b')
当然，这可以进一步优化/专业化。例如，如果你想避免有效的重复，你可以简单地添加一个散列方案和/或一个避免函子。此外，由于参数被保存为引用，因此可以考虑通过删除复制/赋值构造函数和运算符来保护生成器免受可能的错误使用。
时间复杂度在理论置换复杂度范围内。
于 2020-11-14T11:03:53.203 回答