permutations

順列を次々に出します。
例えば、[ 1, 2, 3 ]というリストがあったとして2要素の順列を出すと、

[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

となります。このpermutationsはPythonでは簡単に書けます（本当はライブラリにあるのでこれを書く必要はありません）。

def permutations(v, n):
    if n == 0:
        yield ()
    else:
        for k in xrange(len(v)):
            for a in permutations(v[:k] + v[k+1:], n - 1):
                yield v[k:k+1] + a

これをマネしてC++0xで書きます。しかし、C++にはジェネレータがないのでこんなに簡単には書けません。

template<typename T>
class cPermutations : public cIterable<vector<T>> {
    const vector<T> v;
    int             n;
    int             k;
    shared_ptr<cIterable<vector<T>>>    g;
    vector<T>       w;
    vector<T>       result;
    bool            first;
    
public:
    cPermutations(const vector<T>& w, int m) :
                    v(w), n(m), k(0), result(n), first(true) { }
    
    bool exists_next() {
        if(first) {
            if(n <= 0) {
                bool    ret = first;
                first = false;
                return ret;
            }
            first = false;
            w.resize(v.size() - 1);
            next();
        }
        else {
            if(n == 0)
                return false;
            else if(!g->exists_next()) {
                if(k == (int)v.size() - 1)
                    return false;
                k++;
                next();
            }
        }
        vector<int> a = g->value();
        copy(a.begin(), a.end(), result.begin() + 1);
        return true;
    }
    vector<T> value() const { return result; }
    
private:
    void next() {
        copy(v.begin(), v.begin() + k, w.begin());
        copy(v.begin() + k + 1, v.end(), w.begin() + k);
        result[0] = v[k];
        g = shared_ptr<cIterable<vector<T>>>(new cPermutations(w, n - 1));
        g->exists_next();
    }
};

template<typename T>
shared_ptr<cIterable<vector<T>>> permutations(const vector<T>& v, int n) {
    return shared_ptr<cIterable<vector<int>>>(new cPermutations<T>(v, n));
}

ものすごく遅そうですが、上のPythonよりは速いです。

int main() {
    vector<int> v;
    for(int i = 0; i < 9; i++)
        v.push_back(i);
    auto    g = permutations(v, 9);
    int     counter = 0;
    while(g->exists_next())
        counter++;
    cout << counter << endl;
}