組み合わせを一つずつ表示する。C++コード

最初に

C++で書いた、組み合わせを一つずつ表示するサンプルコードです。

表記

組み合わせ
\, _nC_r = \frac{n!}{r!(n-r)!}\,(n\geq r)

情報

Wikipedia
Combination library

C++コード

/**
* 組み合わせ
*/
template < class BidirectionalIterator >
bool next_combination(BidirectionalIterator first1,
    BidirectionalIterator last1,
    BidirectionalIterator first2,
    BidirectionalIterator last2)
{
    if ((first1 == last1) || (first2 == last2)) return false;
    BidirectionalIterator m1 = last1;
    BidirectionalIterator m2 = last2; --m2;
    while (--m1 != first1 && !(*m1 < *m2));
    bool result = (m1 == first1) && !(*first1 < *m2);
    if (!result) {
        while (first2 != m2 && !(*m1 < *first2)) ++first2;
        first1 = m1;
        std::iter_swap(first1, first2);
        ++first1;
        ++first2;
    }
    if ((first1 != last1) && (first2 != last2)) {
        m1 = last1; m2 = first2;
        while ((m1 != first1) && (m2 != last2)) {
            std::iter_swap(--m1, m2);
            ++m2;
        }
        std::reverse(first1, m1);
        std::reverse(first1, last1);
        std::reverse(m2, last2);
        std::reverse(first2, last2);
    }
    return !result;
}

template < class BidirectionalIterator >
bool next_combination(BidirectionalIterator first,
    BidirectionalIterator middle,
    BidirectionalIterator last) {
    return next_combination(first, middle, middle, last);
}

オンライン実行

コメント 

コメントを残す

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