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には同じように組み合わせを作るための関数が存在しない。そこで全ての組み合わせを作るような関数を探してみた。

落ち着いて素数を数えるんだ！ ということで作ってみた。

半分くらいネタで作ったけど、たぶん近いうちに使う。素数判定は『素因数分解をする［C++］』と同じように簡単なアルゴリズムで、特に難しいアルゴリズムは使ってない。intの範囲を超えるような素数を扱うような予定はないので、とりあえず、これで十分だと判断した。

最小値minと最大値maxが与えられたときに、その範囲から重複しないようにn個の数値を取り出す関数を作りたい。例えば、0～100までの範囲から重複しないように10個の数値を取り出す。

[ 7, 18, 20, 45, 47, 62, 70, 80, 89, 91 ]

とりあえず、３つの方法が考えられたのでそれぞれ実装して速度比較をしてみた。

自分で考えたアルゴリズムの中で、素因数分解をする必要があったので、C++で素因数分解をする関数を書いてみた。調べてみると「p - 1 法」とか「連分数法」とかいろいろなアルゴリズムがあるようだったが、とりあえず、動けばいいので特に難しいアルゴリズムは使わずに実装してみた。