переходить с правой стороны на нечетные позиции и с левой стороны на четные

Question

переходить с правой стороны на нечетные позиции и с левой стороны на четные

Дан непустой массив элементов. Вы должны переместить все элементы с правой стороны в нечетные позиции (начиная с нуля), а с левой стороны — в четные позиции следующим образом:

необработанные данные: 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13

результат: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Какой алгоритм для этого существует с O (n) сложностью по времени? Какова его реализация?

Обратная задача решена Вот (этот алгоритм может быть существенно перевернут, но он будет выглядеть ужасно).

1

algorithm c++in-place time-complexity

Решение

Другие решения

Я наконец нашел решение прямых и обратных задач:

#include <iterator>
#include <algorithm>
#include <type_traits>
#include <limits>
#include <deque>
#include <utility>

#include <cassert>

template< typename Iterator >
struct perfect_shuffle_permutation
{

static_assert(std::is_same< typename std::iterator_traits< Iterator >::iterator_category, std::random_access_iterator_tag >::value,
"!");

using difference_type = typename std::iterator_traits< Iterator >::difference_type;
using value_type = typename std::iterator_traits< Iterator >::value_type;

perfect_shuffle_permutation()
{
for (difference_type power3_ = 1; power3_ < std::numeric_limits< difference_type >::max() / 3; power3_ *= 3) {
powers3_.emplace_back(power3_ + 1);
}
powers3_.emplace_back(std::numeric_limits< difference_type >::max());
}

void
forward(Iterator _begin, Iterator _end) const
{
return forward(_begin, std::distance(_begin, _end));
}

void
backward(Iterator _begin, Iterator _end) const
{
return backward(_begin, std::distance(_begin, _end));
}

void
forward(Iterator _begin, difference_type const _size) const
{
assert(0 < _size);
assert(_size % 2 == 0);
difference_type const left_size_ = *(std::upper_bound(powers3_.cbegin(), powers3_.cend(), _size) - 1);
cycle_leader_forward(_begin, left_size_);
difference_type const rest_ = _size - left_size_;
if (rest_ != 0) {
Iterator middle_ = _begin + left_size_;
forward(middle_, rest_);
std::rotate(_begin + left_size_ / 2, middle_, middle_ + rest_ / 2);
}
}

void
backward(Iterator _begin, difference_type const _size) const
{
assert(0 < _size);
assert(_size % 2 == 0);
difference_type const left_size_ = *(std::upper_bound(powers3_.cbegin(), powers3_.cend(), _size) - 1);
std::rotate(_begin + left_size_ / 2, _begin + _size / 2, _begin + (_size + left_size_) / 2);
cycle_leader_backward(_begin, left_size_);
difference_type const rest_ = _size - left_size_;
if (rest_ != 0) {
Iterator middle_ = _begin + left_size_;
backward(middle_, rest_);
}
}

private :

void
cycle_leader_forward(Iterator _begin, difference_type const _size) const
{
for (difference_type leader_ = 1; leader_ != _size - 1; leader_ *= 3) {
permutation_forward permutation_(leader_, _size);
Iterator current_ = _begin + leader_;
value_type first_ = std::move(*current_);
while (++permutation_) {
assert(permutation_ < _size);
Iterator next_ = _begin + permutation_;
*current_ = std::move(*next_);
current_ = next_;
}
*current_ = std::move(first_);
}
}

void
cycle_leader_backward(Iterator _begin, difference_type const _size) const
{
for (difference_type leader_ = 1; leader_ != _size - 1; leader_ *= 3) {
permutation_backward permutation_(leader_, _size);
Iterator current_ = _begin + leader_;
value_type first_ = std::move(*current_);
while (++permutation_) {
assert(permutation_ < _size);
Iterator next_ = _begin + permutation_;
*current_ = std::move(*next_);
current_ = next_;
}
*current_ = std::move(first_);
}
}

struct permutation_forward
{

permutation_forward(difference_type const _leader, difference_type const _size)
: leader_(_leader)
, current_(_leader)
, half_size_(_size / 2)
{ ; }

bool
operator ++ ()
{
if (current_ < half_size_) {
current_ += current_;
} else {
current_ = 1 + (current_ - half_size_) * 2;
}
return (current_ != leader_);
}

operator difference_type () const
{
return current_;
}

private :

difference_type const leader_;
difference_type current_;
difference_type const half_size_;

};

struct permutation_backward
{

permutation_backward(difference_type const _leader, difference_type const _size)
: leader_(_leader)
, current_(_leader)
, half_size_(_size / 2)
{ ; }

bool
operator ++ ()
{
if ((current_ % 2) == 0) {
current_ /= 2;
} else {
current_ = (current_ - 1) / 2 + half_size_;
}
return (current_ != leader_);
}

operator difference_type () const
{
return current_;
}

private :

difference_type const leader_;
difference_type current_;
difference_type const half_size_;

};

std::deque< difference_type > powers3_;

};

1

Источник

Accepted Answer

Вот только сам алгоритм. Для деталей, объяснений и альтернативных подходов см. ответ для обратной задачи.

Инициализировать указатель на пул правых элементов на N / 2.
Получить самый большой вложенный массив размером 3^К+1
Присоединиться (3^К+1) / 2 элемента от начала массива и (3^К+1) / 2 элемента из пула правосторонних элементов путем замены соответствующих подмассивов. Обновить указатель пула.
Примените алгоритм лидера цикла к частям этого подмассива, начиная с позиций 1, 3, 9, … 3^K-1: переместить элемент в его правильное положение в подмассиве (элементы слева от подмассива в четные позиции, справа — в нечетные позиции), замененный элемент также должен быть перемещен в его правильное положение и т. д. до этой процедуры возвращается в исходное положение.
Рекурсивно обработайте оставшиеся части массива, используя шаги 2 .. 4.

Эта проблема проще, чем обратная задача, упоминаемая в OP, потому что здесь мы должны переупорядочить подмассивы, начиная с более крупных, в том же порядке, что и алгоритм ведения цикла (обратная задача должна делать это отдельно и в обратном порядке). начиная с меньших, чтобы получить O (N) сложность).

1