Programming Magic

C++で全ての順列を作りたければ、STLにnext_permutation関数があり、以下のように簡単に作ることができる。

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

int main(){
  const int n = 3;
  std::vector<int> data;
  // [0, 1, 2, ....]というサイズnの配列を作成
  for(int i=0; i<n; ++i){
    data.push_back(i);
  }
  // 全ての順列を出力
  do{
    std::cout << "[ " << data[0];
    for(unsigned int i=1; i<data.size(); ++i){
      std::cout << ", " << data[i];
    }
    std::cout << " ]" << std::endl;
  }while(next_permutation(data.begin(), data.end()));

  return 0;
}

[ 0, 1, 2 ]
[ 0, 2, 1 ]
[ 1, 0, 2 ]
[ 1, 2, 0 ]
[ 2, 0, 1 ]
[ 2, 1, 0 ]

しかし、STLには同じように組み合わせを作るための関数が存在しない。そこで全ての組み合わせを作るような関数を探してみた。

探してみると全ての組み合わせを作るような関数やクラスなどがいくつか見つかったのだが、その中の「Combination library」のnext_combination関数がすごかった。使い方は以下のようにSTLのnext_permutation関数とほぼ同じようにする。

int main(){
  const int n = 5, r = 3;
  std::vector<int> data;
  // [0, 1, 2, ....]というサイズnの配列を作成
  for(int i=0; i<n; ++i){
    data.push_back(i);
  }
  // 全ての組み合わせを出力
  do{
    std::cout << "[ " << data[0];
    for(unsigned int i=1; i<r; ++i){
      std::cout << ", " << data[i];
    }
    std::cout << " ]" << std::endl;
  }while(next_combination(data.begin(), data.begin()+r, data.end()));

  return 0;
}

[ 0, 1, 2 ]
[ 0, 1, 3 ]
[ 0, 1, 4 ]
[ 0, 2, 3 ]
[ 0, 2, 4 ]
[ 0, 3, 4 ]
[ 1, 2, 3 ]
[ 1, 2, 4 ]
[ 1, 3, 4 ]
[ 2, 3, 4 ]

このように簡単に全ての組み合わせを作れてしまうだけでもすごいのだが、もっとすごいのはその実装だ。next_combination関数の中身は「Algorithms for permutations and combinations, with and without repetitions (PDF注意)」の18～19ページに書いてある。
（※以下のコードのコメントの①～③はあとで説明するために私が追加したもの。）

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 );
}

はっきり言って意味不明だった。解説も書かれてないし、「熟年の開発者ですら書くのが難しい」とか書いてあるし、コードを読んでも何をしているのか、何故これでうまく動くのかわからなかった。さらに、next_combination関数と逆の操作をするprev_combination関数も意味不明。

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

こんなコードをよく書けたと思う（良い意味で）。

ググったりして調べてみたがこれに関する解説なども見つからなかったので、これがどんな操作をしているのか理解するために、以下のように選択されなかった数値も含めて出力してみた。

int main(){
  const int n = 6, r = 3;
  std::vector<int> data;
  // [0, 1, 2, ....]というサイズnの配列を作成
  for(int i=0; i<n; ++i){
    data.push_back(i);
  }
  // 全ての組み合わせを出力
  do{
    std::cout << "[ " << data[0];
    for(unsigned int i=1; i<r; ++i){
      std::cout << ", " << data[i];
    }
    std::cout << " (";
    for(unsigned int i=r; i<n; ++i){
      std::cout << ", " << data[i];
    }
    std::cout << " )]" << std::endl;
  }while(next_combination(data.begin(), data.begin()+r, data.end()));

  return 0;
}

[ 0, 1, 2 (, 3, 4, 5 )]
[ 0, 1, 3 (, 2, 4, 5 )]
[ 0, 1, 4 (, 2, 3, 5 )]
[ 0, 1, 5 (, 2, 3, 4 )]
[ 0, 2, 3 (, 1, 4, 5 )]
[ 0, 2, 4 (, 1, 3, 5 )]
[ 0, 2, 5 (, 1, 3, 4 )]
[ 0, 3, 4 (, 1, 2, 5 )]
[ 0, 3, 5 (, 1, 2, 4 )]
[ 0, 4, 5 (, 1, 2, 3 )]
[ 1, 2, 3 (, 0, 4, 5 )]
[ 1, 2, 4 (, 0, 3, 5 )]
[ 1, 2, 5 (, 0, 3, 4 )]
[ 1, 3, 4 (, 0, 2, 5 )]
[ 1, 3, 5 (, 0, 2, 4 )]
[ 1, 4, 5 (, 0, 2, 3 )]
[ 2, 3, 4 (, 0, 1, 5 )]
[ 2, 3, 5 (, 0, 1, 4 )]
[ 2, 4, 5 (, 0, 1, 3 )]
[ 3, 4, 5 (, 0, 1, 2 )]

何か規則性があるようには見えるが、私にはこれだけでは理解できなかったので、さらに、どの数値が選択されたのかを1,0で表現し、6bitの二進数に変換してみた。そして、1の動きに注目してみると、以下のような赤矢印と青矢印の操作が行われているように見える。

この赤矢印がnext_combination関数のコード中の①、青矢印が②にあたる。①の操作を行っても数値は小さい順に並んだままになるのだが、②の操作では小さい順ではなくなってしまうため、③の操作で数値を並び替えることになる。

最初のr個の値（選択された値）をa[0],a[1],...,a[r-1]、残り（選択されない値）をb[0],b[1],...,b[n-r-1]とすると、以下のような操作をしていることになる。

prev_combination関数でも同じように考えて、それらをまとめたものが上記のコードなのだろう。これでうまくいくのはおそらく数学的に証明されていたりするのだろうが、そこまでは私にはわからなかった。