C++でcombination

STLにはnext_permutaionが用意されているが, next_combinationはない. かつてBoostにはboost/alogorithm/combination.hppというものがあったようだが, 標準装備ではなさそうである (ざっとみてみたが, 下記のものがどうもそれらしい).

https://github.com/hyrise/hyrise/blob/master/third_party/boost/algorithm/combination.hpp

ただ何も考えずにただ実現すれば良いのであれば, 再起を使ってわりと簡単に書ける.

#include <iostream>
#include <vector>

template <typename Tlist, typename Tfunc>
void __combination(
    Tlist const& list, typename Tlist::size_type const n, Tfunc const& func,
    Tlist& tmp, typename Tlist::size_type const i, typename Tlist::size_type const j)
{
    if (i == n)
    {
        func(tmp);
        return;
    }

    for (typename Tlist::size_type k = j; k != list.size() + (1 + i- n); ++k)
    {
        tmp[i] = list[k];
        __combination(list, n, func, tmp, i + 1, k + 1);
    }
}

template <typename Tlist, typename Tfunc>
void combination(
    Tlist const& list, typename Tlist::size_type const n, Tfunc const& func)
{
    Tlist tmp(n);
    __combination(list, n, func, tmp, 0, 0);
}

int main()
{
    std::vector<unsigned int>::size_type m = 5, n = 3;
    std::vector<unsigned int> list(m);
    for (unsigned int i = 0; i < m; ++i)
    {
        list[i] = i + 1;
    }

    combination(
        list, n, [](std::vector<unsigned int> const& a) {
            for (auto i(a.begin()); i != a.end(); ++i)
                std::cout << (*i) << "";
            std::cout << std::endl; });
}

コンパイルして実行すると以下のようになるはずである.

$ g++ -std=c++11 combination.cpp
$ ./a.out
123
124
125
134
135
145
234
235
245
345

ラムダ式のところでC++11を必要とするようだが, それ以外のところではC++11じゃなくてもいけるはずだ.

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
http://www.programming-magic.com/20090123132035/

ちなみにPythonであれば標準関数が使えるので:

import itertools

m, n = 5, 3
l = [i + 1 for i in range(m)]

for a in itertools.combinations(l, n):
    print("".join(str(i) for i in a))

とかなんとかでいける.

http://docs.python.jp/3/library/itertools.html#itertools.combinations

さらに重複組み合せの場合は上のコードに少し手を加えれば良い.

$ diff combination.cpp repeated_combination.cpp 
16c16
<     for (typename Tlist::size_type k = j; k != list.size() + (1 + i- n); ++k)
---
>     for (typename Tlist::size_type k = j; k < list.size(); ++k)
19c19
<         __combination(list, n, func, tmp, i + 1, k + 1);
---
>         __combination(list, n, func, tmp, i + 1, k);

Windows 7のPython 2.7でvtkを使う

とりあえず考えた結果, ParaViewを利用してPython VTKを使えるようにした.

Paraviewのパスが例えば"C:\Program Files (x86)\ParaView 4.3.1"であったとき, コンピュータのプロパティからシステムの詳細設定, 環境変数と選ぶ. ユーザー環境変数でもシステム環境変数でも構わないと思われる.

まず, 新たに"PYTHONPATH"という変数に"C:\Program Files (x86)\ParaView 4.3.1\lib\paraview-4.3\site-packages", "PATH"というおそらく既存の環境変数に"C:\Program Files (x86)\ParaView 4.3.1\bin"を追加する. 既存の変数値に続けて";"の後にパスを書けば追加できる.

これでPython上で"import vtk"として動けば問題ない.

MatplotlibでDISPLAYが設定されていない場合の描画

リモートサーバなどでMatplotlibを利用したグラフの描画をする場合に, いちいちX Windowを飛ばすのは無駄すぎるのでshowではなくsavefigをDISPLAYを利用することなく実行したい.

結論だけ言うとバックエンドを以下のようにして切り替えればいける.

import matplotlib
# Force matplotlib to not use any Xwindows backend.
matplotlib.use('Agg')

http://stackoverflow.com/questions/2801882/generating-a-png-with-matplotlib-when-display-is-undefined

C++でconstポインタとconst参照とconstポインタconst参照

先日イテレータの扱いで少し確認してみたが, 今度はポインタの扱いを確認してみた. 見た目は結構エゲつないが, ポインタもconst参照渡しできる.

int main()
{
  typedef int T;

  T x(10), y(5), z(1);

  T* Tptr(&x);
  T const* Tconstptr(&x); // == const T*
  T* const Tptrconst(&x);
  T const* const Tconstptrconst(&x); // == const T* const

  *Tptr = 20;
  //XXX: *Tconstptr = 20;
  *Tptrconst = 20;
  //XXX: *Tconstptrconst = 20;

  Tptr = &y;
  Tconstptr = &y;
  //XXX: Tptrconst = &y;
  //XXX: Tconstptrconst = &y;

  T*& Tptrref(Tptr);
  T* const& Tptrconstref(Tptr);
  T const* const& Tconstptrconstref(Tptr);
  //XXX: T const*& Tconstptrref(Tptr);
  T const*& Tconstptrref(Tconstptr);

  *Tptrref = 30;
  *Tptrconstref = 30;
  //XXX: *Tconstptrconstref = 30;
  //XXX: *Tconstptrref = 30;

  Tptrref = &z;
  //XXX: Tptrconstref = &z;
  //XXX: Tconstptrconstref = &z;
  Tconstptrref = &z;

  return 0;
}

上は全てgcc version 4.8.2で試した.

T型のconst参照を書く際に"T const&"か"const T&"のどちらに書くべきか(意味的には同じ)考えていたのだが, ポインタ("T*")のconst参照渡しの場合, "T* const&"と"const T*&"は意味が異なってしまうので, "T const&"と書く方がより一般性があるような気がしてきた.

typedef T* TP;
const TP& constTPref(Tptr);
*constTPref = 30;
//XXX: constTPref = &z;

興味深いことに, T型のポインタを一度typedefで定義してやれば"const TP&"のように書ける. ようするに, "const (T*)& == (T*) const&"か"(const T)*&"かの違いである.

こんなことを考え出すとC++は恐ろしいとか言われてしまうのかもしれない.

https://social.msdn.microsoft.com/Forums/ja-JP/24cd88de-2159-4e8b-aee7-3fa30d8647db

C++でのイテレータの参照

C++でイテレータを関数の引数として渡すときに参照渡しをすることにしたが, const参照を渡した場合にイテレータが指している値を変更可能なのかどうか確認してみた.

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> vec = {0, 0, 0, 0, 0};
  std::cout << "vec: ";
  for (auto i: vec) std::cout << i << " ";
  std::cout << std::endl;

  // std::vector<int>::const_iterator const_itr(vec.begin() + 2); //エラー: assignment of read-only location
  // const std::vector<int>::iterator itr(vec.begin() + 2); // OK
  std::vector<int>::iterator itr(vec.begin() + 2);
  const std::vector<int>::iterator& itr_const_ref(itr);
  (*itr_const_ref) = 5;

  std::cout << "vec: ";
  for (auto i: vec) std::cout << i << " ";
  std::cout << std::endl;
  return 0;
}

結果は以下のように無事値が変わっている.

vec: 0 0 0 0 0
vec: 0 0 5 0 0

要するにポインタを渡すときと同様にイテレータ自体を置き換えることはできないが, イテレータが指しているものを変更するのは問題ない. イテレータが指している対象を変更不可能にしたければやはりconst_iteratorをそもそも使う必要があるということだ.

さらに言えば, 参照でなくとも"const std::vector::iterator"も同様にイテレータの変更はできないが, 指している先を書き換えることはできる.

時間スケール

時間スケールについて考える. 普段ならば秒単位で考えれば済む話なのだが, 計算時間を概算する際に何日かかるのか?などと聞かれてすぐに回答できずに困る. スケールだけでも知っておけば概算には十分だ.

秒	分	時間	日	週	月	年
1	60	3,600	86,400	604,800	2,592,000	31,536,000
10^0	10^2	10^3	10^5	10^6	10^6	10^7

およそ15分で1K秒, 3時間で10K秒, 2週間で1M秒ってところか.

sedを練習してみた その1

文字列処理をコマンドで行うためにsedを練習してみた. とりあえず, テキストファイルから特定のサッフィクスではじまる行だけを取り出してきて, そのサフィックスを除いたものを出力してみる.

まずは特定の行を取り出すところ. grepで良いんじゃないかという気もするが練習.

$ sed -e '/^SUFFIX/!d' filename
$ grep '^SUFFIX' filename

sedはファイルから1行ずつパターンスペースと呼ばれる領域に読み込んできてそれに対して指定した処理を加えていく. そして最後にパターンスペースの内容を出力する. 出力を抑制したい場合は"-n"オプションを指定する.

ここではまず"/^SUFFIX/"を使ってアドレスの指定を行なう. ここで指定されたアドレスに対してだけ以降のコマンドが実行される. ただしここで言うコマンドとは続けてあらわれるものだけで, ";"や次の"-e"で指定されるコマンドには関係ない. こうした次のコマンドに影響を与えるためにはパターンスペース自体を変更しなければならない. sedでよく利用される置換コマンドは置換後にパターンスペースを上書きするため, 次のコマンドにも結果が引き継がれる.

正規表現は一般的なもので"/^SUFFIX/"は"^"で行頭をあらわして, 行頭に"SUFFIX"を含む行ということになる. このアドレス表示に続いて"!"でこのアドレス以外の行(アドレス)となる. ここまでがアドレスで次の"d"がコマンドでパターンスペースを削除して, ただちに次の処理を開始する. ようするにこれで"行頭にSUFFIXを含まない行を削除する"となる. "s/^SUFFIX//g"だと"SUFFIX"は消えるが処理は終了されないのでマッチしない行も出力されてしまう.

次にサフィックスを削除する. これは普通に置換で良い.

$ sed -e '/^SUFFIX/!d' -e 's/^SUFFIX//g' filename
$ sed -e '/^SUFFIX/!d;s/^SUFFIX//g' filename
$ grep '^SUFFIX' filename | sed -e 's/^SUFFIX//g'

これで特定のサフィックスではじまる行だけをサフィックスを削除して出力できる.

https://www.gnu.org/software/sed/manual/sed.html