Project Euler 41

http://projecteuler.net/index.php?section=problems&id=41

今度こそちゃんと順列を出すコードを書いた。

itertools.h

#include <iostream>
#include "primes.h"

using namespace std;
using namespace itertools;

template<typename T>
class cPermutations {
    vector<T>   vec;
    vector<int> ref;
    const int   length;
    bool        first;
    
public:
    cPermutations(const vector<T>& v) : vec(v), length(vec.size()) {
        ref = list(range<>(v.size()));
        first = true;
    }
    vector<T> next() {
        if(first) {
            first = false;
            return vec;
        }
        
        int p = down_pos();
        reverse(vec.begin() + p, vec.end());
        reverse(ref.begin() + p, ref.end());
        int n = ref[p-1];
        int m = length;
        int q;
        for(int k = p; k < length; k++) {
            if(n < ref[k] && ref[k] < m) {
                m = ref[k];
                q = k;
            }
        }
        swap(*(vec.begin() + p - 1), *(vec.begin() + q));
        swap(*(ref.begin() + p - 1), *(ref.begin() + q));
        return vec;
    }
    bool exists_next() {
        for(int k = 0; k < length; k++) {
            if(ref[k] + k != length - 1)
                return true;
        }
        return false;
    }
    
private:
    int down_pos() const {
        for(int k = length - 1; k > 0; k--) {
            if(ref[k-1] < ref[k])
                return k;
        }
        throw("no next in cPermutations::down_pos().");
    }
};

template<typename T>
cPermutations<T> perm(vector<T>& v) {
    return cPermutations<T>(v);
}

int perm_prime(int n) {
    auto    p = perm(list(range<>(n, 0, -1)));
    auto    g = filter(primes::is_prime, map([] (vector<int>& v)
                            { return to_number(iterable(v)); }, p));
    return g.exists_next() ? g.next() : 0;
}

int main() {
    cout << head(filter([] (int m) { return m > 0; },
                map(perm_prime, range<>(7, 0, -1)))) << endl;
}