順列を一つずつ表示するサンプル

最初に

C++で書いた、順列を一つずつ表示するサンプルコードです。

表記

順列
\, _nP_r = \frac{n!}{(n-r)!}\,(n\geq r)

情報

Wikipedia

C++コード

#include 
#include 
/**
* 異なるn個のものから、任意にr個とって1列に並べた順列の数で、
* その順列一つ一つを、派生したクラスのメソッドを、そのつど呼び出す。
*/
class Permutation
{
public:
    struct Call
    {
        /**
        * 順列の一つが決まる毎に呼び出される
        * @param [in] v            順列の数値が入っている
        * @param [in] pUserContext 任意のポインタ
        * @return falseを返すと、強制的に順列の処理が終了する。true の場合、継続する。
        */
        virtual bool VPermutationCall(const std::vector &v, void* pUserContext) = 0;
    };
public:
    //! コンストラクタ
    Permutation() {}
    /**
    * 順列
    * 異なるn個のものから、任意にr個とって1列に並べた順列の数
    * @param [in] n 要素数
    * @param [in] r n個のものから重複を許して r個とる数
    * @return falseの場合、強制的に順列の処理が終了した。true の場合、通常終了した。
    */
    size_t Run(int n, int r, Permutation::Call *pCallMethod = nullptr, void* pUserContext = nullptr)
    {
        if (n <= 0 || r <= 0) return false;
        int cnt = 0;
        std::vector vBase;
        std::vector data(n, -1);
        vBase.resize(r, 0);


        for (int i = n - r, j = 0; i= 0) {
                    //m_vBase[data[i]] = a[i];
                    vBase[r - (data[i] + 1)] = n - (i + 1);
                }
            }
            cnt++;
            if (pCallMethod)
                if (! pCallMethod->VPermutationCall(vBase, pUserContext))
                    return cnt;
        } while (next_permutation(data.begin(), data.end()));

        return cnt;
    }
};

オンライン実行

コメント 

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください