perm.h

一个全排列算法的实现

/*
    文件
        Perm.h

    内容
        全排列算法的类声明

    作者
        张锦

    日期
        28.2.2009

    版本
        v0.0
*/

// ---- 包含文件 ----------------------------------------------------------------------------------
    
    #pragma once
    #include <vector>
    using namespace std;

// ---- PermBase 类声明 ---------------------------------------------------------------------------

    template <class Type>
    class Perm 
    {
    // ---- 公共成员 ----------------------------------------------------------------------
   
    public:
        
        // ---- 构造函数和析构函数

        Perm ( Type list[], unsigned int iLength );
        Perm ( Type list[], unsigned int iLength, unsigned int iStartIndex, unsigned int iEndIndex );
        virtual ~Perm (void);
    
        // ---- 公共接口

        Type    *PermOut ( unsigned int iIndex );
        size_t  size (void);

    // ---- 私有成员 ----------------------------------------------------------------------
    
    private:

        // ---- 根据指定的数组生成排列

        void    PermCalculate ( Type list[], unsigned int iStartIndex, unsigned int iEndIndex );

        // ---- 交换数组中的两个元素

        void    Swap ( Type &a, Type &b );

    // ---- 私有成员 ----------------------------------------------------------------------
   
    private:

        int     m_iLength;      // 存储待排列的数组长度
        size_t  m_iPermCount;   // 生成的排列的数量
        std::vector<Type*>   m_vecPerms;     // 存储排列后的各数组
    };

// ---- Perm 类实现----------------------------------------------------------------------------

    /**********************************************************************************************
    *
    *   Perm ( Type list[], unsigned int iLength )
    *
    *   构造函数
    */

    template <class Type>

    Perm<Type>::Perm ( Type list [], unsigned int iLength )
    {
        // 初始化成员变量

        m_iLength       = 0;
        m_iPermCount    = 0;
    
        // 生成排列
    
        Perm ( list, 0, iLength - 1 );
        m_iPermCount    = m_vecPerms.size();
    }

    /**********************************************************************************************
    *
    *   Perm ( Type list[], int iLength, int iStartIndex, int iEndIndex )
    *
    *   构造函数
    */

    template <class Type>

    Perm<Type>::Perm ( Type list[], unsigned int iLength, unsigned int iStartIndex, unsigned int iEndIndex )
    {
        // 初始化成员变量

        m_iLength       = 0;
        m_iPermCount    = 0;

        // 生成排列

        PermCalculate ( list, iStartIndex, iEndIndex );
        m_iPermCount    = m_vecPerms.size();
    }

    /**********************************************************************************************
    *
    *   ~Perm (void)
    *
    *   析构函数
    */

    template <class Type>

    Perm<Type>::~Perm (void)
    {
        m_vecPerms.clear();
    }

    /**********************************************************************************************
    *
    *   PermOut ( int iIndex )
    *
    *   输出指定的排列
    */

    template <class Type>

    Type*   Perm<Type>::PermOut ( unsigned int iIndex )
    {
        if ( m_vecPerms.size() == 0 ||
            iIndex < 0 ||
            iIndex >= m_vecPerms.size() )
        {
            return  0;
        }
        
        return  m_vecPerms [ iIndex ];
    }

    /**********************************************************************************************
    *
    *   size ()
    *
    *   返回生成的排列的数量
    */

    template <class Type>

    size_t  Perm<Type>::size ()
    {
        return  m_iPermCount;
    }

    /**********************************************************************************************
    *
    *  PermCalculate ( Type list[], int iStartIndex, int iEndIndex )
    *
    *   生成全排列，储存到 m_vecPerms 中
    */

    template <class Type>

    void   Perm<Type>::PermCalculate ( Type list [], unsigned int iStartIndex, unsigned int iEndIndex )
    {
        // 递归出口

        if ( iStartIndex == iEndIndex )
        {
            // 复制当前数组到临时数组中

            Type    *pTempPerm      = new Type [ m_iLength ];
            for ( unsigned int i=0 ; i<=iEndIndex ; ++i )
            {
                pTempPerm [ i ]     = list [ i ];
            }

            // 将临时数组指针插入到 m_vecPerms

            m_vecPerms.push_back ( pTempPerm );

            return;
        }

        // 循环递归调用排列生成函数

        for ( unsigned int i = iStartIndex ; i<= iEndIndex ; ++ i )
        {
            Swap ( list [iStartIndex], list [ i ] );
            PermCalculate ( list, iStartIndex + 1, iEndIndex );
            Swap ( list [iStartIndex], list [ i ] );
        }
    }

    /**********************************************************************************************
    *
    *   void    Swap ( Type &a, Type &b )
    *
    *   交换数组中两元素
    */

    template <class Type>

    void    Perm<Type>::Swap ( Type &a, Type &b )
    {
        Type    temp;
        temp    = a;
        a       = b;
        b       = temp;
    }