Я улучшил алгоритм chmike. Эта функция соответствует его для всех 11! перестановки (0..10) передаются как вектор переупорядочения. Также не изменяет вектор переупорядочения.
template< class T >
void reorder(vector<T> &v, vector<size_t> const &order ) {
for ( int s = 1, d; s < order.size(); ++ s ) {
for ( d = order[s]; d < s; d = order[d] ) ;
if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] );
}
}
Вот версия в стиле STL, в которую я вложил немного больше усилий. Он примерно на 47% быстрее (то есть почти вдвое быстрее (0..10)!), Потому что он делает все перестановки как можно раньше, а затем возвращается. Вектор переупорядочения состоит из ряда орбит, и каждая орбита переупорядочивается при достижении своего первого члена. Это быстрее, когда последние несколько элементов не содержат орбиты.
template< typename order_iterator, typename value_iterator >
void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v ) {
typedef typename iterator_traits< value_iterator >::value_type value_t;
typedef typename iterator_traits< order_iterator >::value_type index_t;
typedef typename iterator_traits< order_iterator >::difference_type diff_t;
diff_t remaining = order_end - 1 - order_begin;
for ( index_t s = index_t(), d; remaining > 0; ++ s ) {
for ( d = order_begin[s]; d > s; d = order_begin[d] ) ;
if ( d == s ) {
-- remaining;
value_t temp = v[s];
while ( d = order_begin[d], d != s ) {
swap( temp, v[d] );
-- remaining;
}
v[s] = temp;
}
}
}
И, наконец, просто чтобы раз и навсегда ответить на вопрос, вариант, который уничтожает вектор переупорядочения. (Это заполняет его -1.) Это примерно на 16% быстрее, чем в предыдущей версии. Этот использует отвратительный тип, но разберись с ним. Это охватывает 11! ~ = 40 млн. Перестановок из 11 символов за 4,25 секунды, не считая накладных расходов, на моем ноутбуке с частотой 2,2 ГГц.
template< typename order_iterator, typename value_iterator >
void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v ) {
typedef typename iterator_traits< value_iterator >::value_type value_t;
typedef typename iterator_traits< order_iterator >::value_type index_t;
typedef typename iterator_traits< order_iterator >::difference_type diff_t;
diff_t remaining = order_end - 1 - order_begin;
for ( index_t s = index_t(); remaining > 0; ++ s ) {
index_t d = order_begin[s];
if ( d == (diff_t) -1 ) continue;
-- remaining;
value_t temp = v[s];
for ( index_t d2; d != s; d = d2 ) {
swap( temp, v[d] );
swap( order_begin[d], d2 = (diff_t) -1 );
-- remaining;
}
v[s] = temp;
}
}