next_combinationを実装してみた

前置き

next_permutationがあるならnext_combinationがあってもいいじゃないか、というわけでnext_combinationです。

next_combinationでググると、実装されたものもたくさん見つかるのですが、どれもなかなか理解するのが大変で、そんな中でも比較的私の頭でも理解できそうだったものを参考に、勉強のために改めて自分で実装し直してみました。

なお、参考にさせていただいた記事はこちらです。C++でnCkやnPkを全列挙する関数
ありがとうございます。

実装

next_combination

template <typename T> bool next_combination(const T first, const T last, int k) {
    const T subset = first + k;
    // empty container | k = 0 | k == n 
    if (first == last || first == subset || last == subset) {
        return false;
    }
    T src = subset;
    while (first != src) {
        src--;
        if (*src < *(last - 1)) {
            T dest = subset;
            while (*src >= *dest) {
                dest++;
            }
            iter_swap(src, dest);
            rotate(src + 1, dest + 1, last);
            rotate(subset, subset + (last - dest) - 1, last);
            return true;
        }
    }
    // restore
    rotate(first, subset, last);
    return false;
}

概要

「次の組み合わせ」が先頭k個に、その組み合わせに使われていない数はソートされた状態で後ろに繋がるようになっています。次の組み合わせがなければfalseが返ります。
後ろがソートされていることにより、次の数が容易に取り出せるような実装になっています。多分。

使い方

まずソートされた列を用意します。（前述の通り、列の後半部分はソートされていることが前提なので、next_permutationとは違ってソート済みでない列を最初に渡してしまうと動作しません）
引数には、next_permutationのようにイテレータを渡すとともに、nCkのkも渡します。
組み合わせとして見るべき要素は、先頭のk要素となります。

vector<int> v{1, 2, 3, 4, 5, 6, 7};
do {
    for (int i = 0; i < k; i++) {
        cout << v[i] << " ";
    }
    cout << "| ";
    for (int i = k; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
} while(next_combination(v.begin(), v.end(), k));

/*
1 2 3 | 4 5 6 7 
1 2 4 | 3 5 6 7 
1 2 5 | 3 4 6 7 
1 2 6 | 3 4 5 7 
1 2 7 | 3 4 5 6 
1 3 4 | 2 5 6 7 
1 3 5 | 2 4 6 7 
1 3 6 | 2 4 5 7 
1 3 7 | 2 4 5 6 
1 4 5 | 2 3 6 7
...
*/

使ってみた

実戦投入したものがこちらです。
https://atcoder.jp/contests/cpsco2019-s1/submissions/8827591

作っておいてこんなことをいうのも何ですが、next_permutationほど頻繁に使う機会があるものではないですね。