Кнут подробно описывает комбинации и перестановки в Искусство компьютерного программирования , том 1. Вот реализация одного из его алгоритмов, которые я написал несколько лет назад (не ненавижу стиль,его древний код):
#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
template<class BidirectionalIterator, class Function, class Size>
Function _permute(BidirectionalIterator first, BidirectionalIterator last, Size k, Function f, Size n, Size level)
{
// This algorithm is adapted from Donald Knuth,
// "The Art of Computer Programming, vol. 1, p. 45, Method 1"
// Thanks, Donald.
for( Size x = 0; x < (n-level); ++x ) // rotate every possible value in to this level's slot
{
if( (level+1) < k )
// if not at max level, recurse down to twirl higher levels first
f = _permute(first,last,k,f,n,level+1);
else
{
// we are at highest level, this is a unique permutation
BidirectionalIterator permEnd = first;
advance(permEnd, k);
f(first,permEnd);
}
// rotate next element in to this level's position & continue
BidirectionalIterator rotbegin(first);
advance(rotbegin,level);
BidirectionalIterator rotmid(rotbegin);
rotmid++;
rotate(rotbegin,rotmid,last);
}
return f;
}
template<class BidirectionalIterator, class Function, class Size>
Function for_each_permutation(BidirectionalIterator first, BidirectionalIterator last, Size k, Function fn)
{
return _permute<BidirectionalIterator,Function,Size>(first, last, k, fn, distance(first,last), 0);
}
template<class Elem>
struct DumpPermutation : public std::binary_function<bool, Elem* , Elem*>
{
bool operator()(Elem* begin, Elem* end) const
{
cout << "[";
copy(begin, end, ostream_iterator<Elem>(cout, " "));
cout << "]" << endl;
return true;
}
};
int main()
{
int ary[] = {1, 2, 3};
const size_t arySize = sizeof(ary)/sizeof(ary[0]);
for_each_permutation(&ary[0], &ary[arySize], 2, DumpPermutation<int>());
return 0;
}
Вывод этой программы:
[1 2 ]
[1 3 ]
[2 3 ]
[2 1 ]
[3 1 ]
[3 2 ]
Если вы хотите, чтобы ваши комбинации включали повторяющиеся элементы, такие как [11] [22] и [33],Вы можете сгенерировать свой список комбинаций, используя алгоритм, приведенный выше, а затем добавить к сгенерированному списку новые элементы, выполнив что-то вроде этого:
for( size_t i = 0; i < arySize; ++i )
{
cout << "[";
for( int j = 0; j < k; ++j )
cout << ary[i] << " ";
cout << "]" << endl;
}
... и вывод программы теперь станет:
[1 2 ]
[1 3 ]
[2 3 ]
[2 1 ]
[3 1 ]
[3 2 ]
[1 1 ]
[2 2 ]
[3 3 ]