Переместите все нечетные позиционированные элементы влево и вправо на половину места

Ответ 1

• Получить наибольший суб-массив размером 3 ^k +1
• Применить алгоритм лидера цикла к частям этого подматрица, начиная с позиций 1, 3, 9,... 3 ^k-1: переместить элемент в нужное положение в поддиапазоне (даже индексированные элементы слева от поддиапазона с нечетным индексом - справа), заменяемый элемент также должен быть перемещен в нужное положение и т.д., пока эта процедура не вернется в исходную позицию. В этой статье дается теоретико-числовое объяснение того, почему такой выбор начальных позиций перетасовывает подматрицу в правильный порядок.
• Обработать оставшиеся части массива рекурсивно, используя шаги 1 и 2.
• Теперь нам нужно только присоединиться к переупорядоченным частям. Начните с меньших подмассивов в конце всего массива. Чтобы обменивать половинки подматрицы, используйте обратный алгоритм: reverse (reverse (a), reverse (b)); или, для половин массива одинакового размера, используйте парные свопы.
• Теперь все позиционируемые элементы расположены слева. Чтобы получить их справа, по мере необходимости, обмениваем элементы я и я + N/2 для всех я = 0.. N/2-1.

Алгоритм на месте, сложность по времени - O (N).

Пример:

0 1 2 3 4  5 6 7 8 9   10 11 (the original array)
0 1 2 3 4  5 6 7 8 9 # 10 11 (split to sub-arrays)
0 2 4 3 8  1 6 5 7 9 # 10 11 (first cycle leader iteration, starting with 1)
0 2 4 6 8  1 3 5 7 9 # 10 11 (second cycle leader iteration, starting with 3)
0 2 4 6 8  9 7 5 3 1 # 10 11(2nd half of 1st part& 1st half of 2nd part reversed)
0 2 4 6 8 10 1 3 5 7    9 11 (both halves reversed together)

Изменение этого алгоритма, которому не требуется шаг 5:

• На шаге 1 получите наибольшую подматрицу, имеющую размер 3 ^k -1.
• На шаге 2 переместите элементы с четным индексом справа от суб-массива с нечетным индексом слева. Используйте начальные позиции 0, 2, 8,... 3 ^k-1 -1 для алгоритма лидерства.

Здесь используется другой алгоритм O (N log N), который не нуждается в теоретико-числовых доказательствах:

• Переинтерпретируйте свой массив как последовательность одноэлементных матриц 2 * 2, перенесите эти матрицы.
• Переинтерпретировать результат как последовательность двухэлементных матриц 2 * 2 и перенести их.
• Продолжайте, когда размер матриц меньше размера массива.
• Теперь нам нужно только объединить переупорядоченные части (точно так же, как в предыдущем алгоритме).
• Обмен элементами левой и правой половин массива (точно так же, как в предыдущем алгоритме).

Пример:

0  1   2 3   4 5   6 7  (the original array)
[0 2] [1 3] [4 6] [5 7] (first transposition)
[0 2] [4 6] [1 3] [5 7] (second transposition)

Эта проблема является лишь частным случаем Транзирование на месте матрицы.

Ответ 2

Я попытался реализовать, как сказал Евгений Клюев, и вот результат:

#pragma once

#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_;

};

Ответ 3

Я изменил код здесь, чтобы получить этот алгоритм:

void PartitionIndexParity(T arr[], size_t n)
{
    using std::swap;
    for (size_t shift = 0, k; shift != n; shift += k)
    {
        k = (size_t)pow(3, ceil(log(n - shift) / log(3)) - 1) + 1;
        for (size_t i = 1; i < k; i *= 3)  // cycle-leader algorithm
        {
            size_t j = i;
            do { swap(arr[(j = j / 2 + (j % 2) * (k / 2)) + shift], arr[i + shift]); } while (j != i);
        }

        for (size_t b = shift / 2, m = shift, e = shift + (k - k / 2), i = m; shift != 0 && k != 0; )  // or just use std::rotate(arr, b, m, e)
        {
            swap(arr[b++], arr[i++]);
            if (b == m && i == e) { break; }
            if (b == m) { m = i; }
            else if (i == e) { i = m; }
        }
    }
}

Ответ 4

Здесь реализация Java алгоритма Peiyush Jain:

import java.util.Arrays;

public class InShuffle {
    public static void main(String[] args) {
        Integer[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };

        inShuffle(nums);

        System.out.println(Arrays.toString(nums));
    }

    public static <T> void inShuffle(T[] array) {
        if (array == null) {
            return;
        }

        inShuffle(array, 0, array.length - 1);
    }

    private static <T> void inShuffle(T[] array, int startIndex, int endIndex) {
        while (endIndex - startIndex + 1 > 1) {
            int size = endIndex - startIndex + 1;
            int n = size / 2;
            int k = (int)Math.floor(Math.log(size + 1) / Math.log(3));
            int m = (int)(Math.pow(3, k) - 1) / 2;

            rotateRight(array, startIndex + m, startIndex + n + m - 1, m);

            for (int i = 0, cycleStartIndex = 0; i < k; ++i, cycleStartIndex = cycleStartIndex * 3 + 2) {
                permuteCycle(array, startIndex, cycleStartIndex, 2 * m + 1);
            }

            endIndex = startIndex + 2 * n - 1;
            startIndex = startIndex + 2 * m;
        }
    }

    private static <T> void rotateRight(T[] array, int startIndex, int endIndex, int amount) {
        reverse(array, startIndex, endIndex - amount);
        reverse(array, endIndex - amount + 1, endIndex);
        reverse(array, startIndex, endIndex);
    }

    private static <T> void reverse(T[] array, int startIndex, int endIndex) {
       for (int leftIndex = startIndex, rightIndex = endIndex; leftIndex < rightIndex; ++leftIndex, --rightIndex) {
           swap(array, leftIndex, rightIndex);
       }
    }

    private static <T> void swap(T[] array, int index1, int index2) {
        T temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    private static <T> void permuteCycle(T[] array, int offset, int startIndex, int mod) {
        for (int i = ((2 * startIndex + 2) % mod) - 1; i != startIndex; i = ((2 * i + 2) % mod) - 1) {
            swap(array, offset + i, offset + startIndex);
        }
    }
}

И выполнение out-shuffle так же просто, как:

public static <T> void outShuffle(T[] array) {
    if (array == null) {
       return;
    }

    inShuffle(array, 1, array.length - 1);
}

Ответ 5

public class OddToLeftEvenToRight {

    private static void doIt(String input){

        char[] inp = input.toCharArray();
        int len = inp.length;

        for(int j=1; j< len; j++)
        {
            for(int i=j; i<len-j; i+=2)
            {

                swap(inp, i, i+1);

            }
        }

        System.out.print(inp);

    }

    private static void swap(char[] inp, int i, int j) {

        char tmp = inp[i];
        inp[i]= inp[j];
        inp[j]=tmp;

    }

    public static void main(String[] args)
    {

        doIt("a1b");
    }

}

Эта программа делает это в O (n ^ 2).