スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

C++で配列の全順列組み合わせを作るマクロ

C++で配列の全順列組み合わせを作るマクロを作ってみました。

#define PERMUTATION_FOR(CONTAINER) \
    std::sort((CONTAINER).begin(), (CONTAINER).end()); \
    for ( \
        bool ON_PERMUTATION_FOR = true; \
        ON_PERMUTATION_FOR; \
        ON_PERMUTATION_FOR = std::next_permutation((CONTAINER).begin(), (CONTAINER).end()))


単純にnext_permutationをforeach敵な構文にしただけのマクロです。

使用法については、たとえばこんな風なテストコードを書くと、、、

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>


#define PERMUTATION_FOR(CONTAINER) \
    std::sort((CONTAINER).begin(), (CONTAINER).end()); \
    for ( \
        bool ON_PERMUTATION_FOR = true; \
        ON_PERMUTATION_FOR; \
        ON_PERMUTATION_FOR = std::next_permutation((CONTAINER).begin(), (CONTAINER).end()))


using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    PERMUTATION_FOR(v)
    {
        for (size_t i = 0; i < v.size(); ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }

    return 0;
}



これを実行すると、下記のように順列組み合わせの総当りを得ることが出来ます。

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1



順列の総当りはプロコンなどで良く使用されているようですが、ある問題に対して、その解法がわからないが、
逆問題は解ける、という場合に総当りで逆問題を解くという場合に使用されます。

たとえば、下記に例をひとつ。
#include "stdafx.h"

#include <iostream>
#include <vector>
#include <algorithm>


#define PERMUTATION_FOR(CONTAINER) \
    std::sort((CONTAINER).begin(), (CONTAINER).end()); \
    for ( \
        bool ON_PERMUTATION_FOR = true; \
        ON_PERMUTATION_FOR; \
        ON_PERMUTATION_FOR = std::next_permutation((CONTAINER).begin(), (CONTAINER).end()))


using namespace std;



bool is_sorted(const vector<int>& v)
{
    for (size_t i = 1; i < v.size(); ++i)
    {
        if (v[i - 1] > v[i])
            return false;
    }

    return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> v;
    v.push_back(3);
    v.push_back(1);
    v.push_back(2);

    PERMUTATION_FOR(v)
    {
        if (is_sorted(v))
            break;
    }

    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}


このサンプルでは、順列組み合わせからソートを行っています。
ソートのような簡単な問題であれば既知のアルゴリズムを使えば良いわけですが、上記サンプルの場合、
ソートのアルゴリズムはわからないが、ある配列がソートされているかどうかは判断できる、という場合、
全ての順列組み合わせを試して、その中からソートされている組み合わせを見つければ、それを解とする、
という手順になっています。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

カレンダー
10 | 2017/11 | 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -
最新記事
カテゴリ
Qt (21)
SDL (2)
MFC (2)
検索フォーム
月別アーカイブ
最新コメント
最新トラックバック
RSSリンクの表示
リンク
リンク(管理用)
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。