Steinhaus–Johnson–Trotter algorithm の実装

• Steinhaus–Johnson–Trotter algorithm - Wikipedia, the free encyclopedia

Permutation.h

#ifndef PERMUTATION_H
#define PERMUTATION_H

#include <vector>

class Permutation
{
public:
    Permutation(int* begin, int* end);
    bool isIdentity() const;
    Permutation& operator ++ ();
    Permutation operator ++ (int);
    const int* begin() const;
    const int* end() const;
    int operator [] (int i) const;

private:
    void init();

    std::vector<int> source_;
    std::vector<int> current_;
    std::vector<int> c_;
    std::vector<bool> d_;
    int x_;
    int i_;
    bool identity_;
};

#endif//PERMUTATION_H

Permutation.cpp

#include "Permutation.h"

#include <algorithm>

Permutation::Permutation(int* begin, int* end) :
    source_(begin, end),
    current_(begin, end),
    c_(std::distance(begin,end)),
    d_(std::distance(begin,end), true),
    x_(0),
    i_(std::distance(begin,end) - 1),
    identity_(true)
{
}

void Permutation::init()
{
    std::copy(source_.begin(), source_.end(), current_.begin());
    std::fill(c_.begin(), c_.end(), 0);
    std::fill(d_.begin(), d_.end(), false);
    x_ = 0;
    i_ = current_.size() - 1;
    identity_ = true;

}

bool Permutation::isIdentity() const
{
    return identity_;
}

Permutation& Permutation::operator ++ ()
{
    identity_ = false;
    do
    {
        if(c_[i_] < i_)
        {
            int index = d_[i_] ? (i_ - c_[i_] + x_) : (c_[i_] + x_ + 1);
            std::swap(current_[index - 1], current_[index]);
            ++c_[i_];
            i_ = current_.size() - 1;
            x_ = 0;
            return *this;
        }
        else
        {
            if(d_[i_])
            {
                ++x_;
            }
            d_[i_] = ! d_[i_];
            c_[i_] = 0;
            --i_;
        }
    } while(i_ > 0);
    init();
    return *this;
}

Permutation Permutation::operator ++ (int)
{
    Permutation result(*this);
    ++(*this);
    return result;
}

const int* Permutation::begin() const
{
    return &(*current_.begin());
}

const int* Permutation::end() const
{
    return &*current_.end();
}

int Permutation::operator [] (int i) const
{
    return current_[i];
}

PermutatinTest.cpp

#include "Permutation.h"

#include <iostream>

std::ostream& operator << (std::ostream& out, const Permutation& perm)
{
    std::copy(perm.begin(), perm.end(), std::ostream_iterator<int>(out, " "));
    return out;
}

int main(int, char* [])
{
    int a[] = { 2, 4, 6, 8 };
    Permutation perm(a, a + 4);

    do
    {
        std::cout << perm++ << std::endl;
    } while( ! perm.isIdentity());

    return 0;
}

ビルド&実行。

$ g++ -o PermutationTest Permutation.cpp PermutationTest.cpp 
$ ./PermutationTest 
2 4 6 8 
2 4 8 6 
2 8 4 6 
8 2 4 6 
8 2 6 4 
2 8 6 4 
2 6 8 4 
2 6 4 8 
6 2 4 8 
6 2 8 4 
6 8 2 4 
8 6 2 4 
8 6 4 2 
6 8 4 2 
6 4 8 2 
6 4 2 8 
4 6 2 8 
4 6 8 2 
4 8 6 2 
8 4 6 2 
8 4 2 6 
4 8 2 6 
4 2 8 6 
4 2 6 8 

問題は。「CiNii 論文 -  アルゴリズムの最近の動向：7. 順列の生成法」の中の「2.2 繰り返し的方法*1」をC++のコードにしてみただけで、中身をキチンと理解してないところ。リクツはわかるのだけれども。

*1:ページの右にあるプレビューを開いてください。プレビューにはリンクできないようです。