順列.cpp

[詳解]

#include <algorithm>
#include <iostream>
#include "順列.h"

unsigned int 階乗( const unsigned int 値, const unsigned int 開始値 = 1 )
{
    if ( 値 <= 開始値 ) { return 1; }
    return 値 * 階乗( 値 - 1, 開始値 );
}


template<class T> void 全表示本体( T* ptr )
{
    ptr->初期化();
    int cnt = 1;
    for ( std::vector<unsigned int> seq = ptr->次(); seq.size(); seq = ptr->次() )
    {
        std::wcout << cnt++ << L":";
        for ( auto it = seq.rbegin(); it != seq.rend(); ++it )
        {
            std::wcout << wchar_t( L'a' + *it );
        }
        std::wcout << std::endl;
    }
    std::wcout << L"あるべき長さ = " << ptr->総数() << std::endl;
}


順列::順列( const unsigned int 元数, const unsigned int 取得長さ )
    : m元数( 元数 ), m取得長さ( 取得長さ ? 取得長さ : 元数 )
{
}


std::vector<unsigned int> 順列::次()
{
    // 各桁の値が重複しない昇順という感じの単純な実装です。
    // ここでは添え字の小さいほうが下位桁相当。
    if ( m現況.size() == 0 )
    {
        for ( unsigned int i = 0; i < m取得長さ; ++i )
        {
            m現況.push_back( m取得長さ - 1 - i );
        }
        return m現況;
    }
    std::vector<unsigned int> sub( m現況 );
    auto subIt = sub.begin();
    for ( unsigned int 桁 = 0; 桁 < m取得長さ; ++桁 )
    {
        ++subIt;
        for ( unsigned int 値 = m現況[ 桁 ] + 1; 値 < m元数; ++値 )
        {
            if ( std::find( subIt, sub.end(), 値 ) != sub.end() )
            {
                continue;
            }
            m現況[ 桁 ] = 値;
            unsigned int c = 0;
            for ( unsigned int k = 桁; k > 0; --k )
            {
                for ( ; ; ++c )
                {
                    if ( c != 値 && std::find( subIt, sub.end(), c ) == sub.end() )
                    {
                        m現況[ k - 1 ] = c++;
                        break;
                    }
                }
            }
            return m現況;
        }
    }
    m現況.clear();
    return m現況;
}


unsigned int 順列::総数() const
{
    return 階乗( m元数, m元数 - m取得長さ );
}


void 順列::全表示()
{
    全表示本体( this );
}


組み合わせ::組み合わせ( const unsigned int 元数, const unsigned int 取得長さ )
    : m順列( 元数, 取得長さ )
{
}


std::vector<unsigned int> 組み合わせ::次()
{
    // 順列の中から各桁の値が昇順になっているものだけ返しています。
    std::vector<unsigned int> r( m順列.次() );
    for ( ; r.size(); r = m順列.次() )
    {
        auto it = r.begin();
        unsigned int prev = *it;
        for ( ++it; it != r.end(); ++it )
        {
            if ( prev <= *it ) { break; }
            prev = *it;
        }
        if ( it == r.end() ) { break; } 
    }
    return r;
}


unsigned int 組み合わせ::総数() const
{
    return 階乗( m順列.m元数, m順列.m元数 - m順列.m取得長さ ) / 階乗( m順列.m取得長さ );
}


void 組み合わせ::全表示()
{
    全表示本体( this );
}