正と負の整数を含む配列を指定して、奇数のインデックス付き要素をすべて左に移動し、偶数のインデックス付き要素を右に移動します。
問題の難しい部分は、順序を維持しながらインプレースで実行することです。
例えば
7, 5, 6, 3, 8, 4, 2, 1
出力は次のようになります。
5, 3, 4, 1, 7, 6, 8, 2
順序が重要でない場合は、クイック ソートの partition() アルゴリズムを使用できたはずです。
O(N)でそれを行う方法は?
正と負の整数を含む配列を指定して、奇数のインデックス付き要素をすべて左に移動し、偶数のインデックス付き要素を右に移動します。
問題の難しい部分は、順序を維持しながらインプレースで実行することです。
例えば
7, 5, 6, 3, 8, 4, 2, 1
出力は次のようになります。
5, 3, 4, 1, 7, 6, 8, 2
順序が重要でない場合は、クイック ソートの partition() アルゴリズムを使用できたはずです。
O(N)でそれを行う方法は?
アルゴリズムはインプレースであり、時間計算量は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を必要としないこのアルゴリズムのバリエーション:
これは、数論的証明を必要としない、さまざまなO(N log N)インプレースアルゴリズムです。
例:
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)
この問題は、インプレース行列転置の特殊なケースにすぎません。
Evgeny Kluevが言ったように実装しようとしましたが、結果は次のとおりです。
#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_;
};
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) でそれを行います。
このアルゴリズムを取得するために、ここのコードを変更しました。
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; }
}
}
}