What's the most widely used existing library in C++ to give all the combination and permutation of k elements out of n elements?
I am not asking the algorithm but the existing library or methods.
Thanks.
5 Answers
Combinations: from Mark Nelson's article on the same topic we have next_combination Permutations: From STL we have 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;
}
@ Charles Bailey above:
I could be wrong, but I think the first two algorithms above does not remove duplicates between first and mid? Maybe I am not sure how to use it.
4 choose 2 example:
12 34
12 43 (after sort)
13 24 (after next_permutation)
13 42 (after sort)
14 23 (after next_permutation)
14 32 (after sort)
21 34 (after next_permutation)
So I added a check to see if the value in italics is in order before returning, but definitely wouldn't have thought of the part you wrote though (very elegant! thanks!).
Not fully tested, just cursory tests..
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;
}
Maybe it's already stated within the previous answers, but here I cannot find a full generic way for this with respect to the parameter types and I also didn't find it within existing library routines besides Boost. This is a generic way I needed during test case construction for scenarios with a wide spread of various parameter variations. Maybe it's helpful to you too, at least for similar scenarios. (Usable for permutation and combination with minor changes in doubt)
#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;
};
Possible usage:
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));
Generates:
(1, -1, 'a')
(2, -1, 'a')
(1, -2, 'a')
(2, -2, 'a')
(1, -1, 'b')
(2, -1, 'b')
(1, -2, 'b')
(2, -2, 'b')
For sure, this can be further optimized/specialized. For instance you can simply add a hashing scheme and/or an avoid functor if you want to avoid effective repetitions. Also, since the parameters are held as references, one might consider to protect the generator from possible error-prone usage via deleting copy/assignement constructors and operators.
Time complexity is within the theoretical permutation complexity range.
Related