1

空でないアイテムの配列が与えられます。次のように、すべてのアイテムを右側から奇数の位置 (0 から始まる) に移動し、左側から偶数の位置に移動する必要があります。

生データ: 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) 時間の複雑さで、これにはどのようなインプレース アルゴリズムが存在しますか? その実装は何ですか？

逆の問題はここで解決されます(このアルゴリズムは本質的に逆にすることができますが、見栄えが悪くなります)。

4

2 に答える 2

1

私はついに直接問題と逆問題の解決策を見つけました：

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

};
于 2012-11-09T22:25:10.813 に答える
1

これはアルゴリズム自体だけです。詳細、説明、および代替アプローチについては、逆問題の回答を参照してください。

  1. 右側の要素のプールへのポインタをN/2に初期化します。
  2. サイズ3k +1の最大のサブアレイを取得します
  3. 適切なサブ配列を交換することにより、配列の先頭から（3 k +1）/ 2要素を結合し、右側の要素のプールから（3 k +1）/2要素を結合します。プールポインタを更新します。
  4. 位置1、3、9、... 3 k-1から開始して、このサブ配列の部分にサイクルリーダーアルゴリズムを適用します。要素をサブ配列内の適切な位置に移動します（サブ配列の左側から偶数の位置（右から奇数の位置）では、この手順が開始位置に戻るまで、交換された要素も適切な位置などに移動する必要があります。
  5. 手順2..4を使用して、配列の残りの部分を再帰的に処理します。

この問題は、OPで参照される逆問題よりも単純です。これは、ここでは、サイクルリーダーアルゴリズムを実行するのと同じ順序で、大きい配列からサブ配列を並べ替える必要があるためです（逆問題は、個別に逆の順序で実行する必要があります）。 、小さいものから始めて、O（N）の複雑さを取得します）。

于 2012-11-09T19:48:27.073 に答える