クイックリファレンス: 式の演算子と関数
以下の表は、qbpp::Exprオブジェクトで利用可能な演算子と関数をまとめたものです。
| 演算子/関数 | 演算子記号/関数名 | 関数タイプ | 戻り値の型 | 引数の型 |
|---|---|---|---|---|
| 型変換 | toExpr() | グローバル | qbpp::Expr | ExprType |
| 代入 | = | メンバ | qbpp::Expr | ExprType |
| 二項演算子 | +, -, * | グローバル | qbpp::Expr | ExprType-ExprType |
| 複合代入演算子 | +=, -=, *= | メンバ | qbpp::Expr | ExprType |
| 除算 | / | グローバル | qbpp::Expr | ExprType-Int |
| 複合除算 | /= | メンバ | qbpp::Expr | Int |
| 単項演算子 | +, - | グローバル | qbpp::Expr | ExprType |
| 比較（等値） | == | グローバル | qbpp::Expr（制約式） | ExprType-Int |
| 比較（範囲比較） | <= <= | グローバル | qbpp::Expr（制約式） | IntInf-ExprType-IntInf |
| 二乗 | sqr() | グローバル | qbpp::Expr | ExprType |
| 二乗 | sqr() | メンバ | qbpp::Expr | - |
| 最大公約数 | gcd() | グローバル | Int | ExprType |
| 簡約化 | simplify(), simplify_as_binary(), simplify_as_spin() | グローバル | qbpp::Expr | ExprType |
| 簡約化 | simplify(), simplify_as_binary(), simplify_as_spin() | メンバ | qbpp::Expr | - |
| 評価 | operator() | メンバ | Int | ExprType-qbpp::MapList |
| 置換 | replace() | グローバル | qbpp::Expr | ExprType-qbpp::MapList |
| 置換 | replace() | メンバ | qbpp::Expr | qbpp::MapList |
| バイナリ/スピン変換 | binary_to_spin(), spin_to_binary() | グローバル | qbpp::Expr | ExprType |
| バイナリ/スピン変換 | binary_to_spin(), spin_to_binary() | メンバ | qbpp::Expr | - |
| スライス（タプルインデックス） | operator() | メンバ | Array | - |
| 連結 | concat() | グローバル | Array | Array-Array |
| 連結（スカラー付き） | concat() | グローバル | Array | Expr-Array |
型変換: qbpp::toExpr()
グローバル関数qbpp::toExpr()は引数をqbpp::Exprインスタンスに変換して返します。 引数は以下のいずれかです:
- 整数
- 変数（
qbpp::Var） - 積項（
qbpp::Term） - 式（
qbpp::Expr）– この場合、変換は行われません
これらの引数の型を総称してExprTypeと呼びます。
式関連の型: ExprType
ExprTypeという用語は、qbpp::Exprオブジェクトに変換可能な型のカテゴリを示します。
整数関連の型: IntとIntInf
Int: 通常の整数IntInf: 整数、-qbpp::inf、または+qbpp::infのいずれかで、無限の境界を表します。
グローバル関数とメンバ関数
qbpp::Exprに関連する演算子と関数は2つの形式で提供されます:
- グローバル関数: 少なくとも1つのExprType引数を取り、通常は入力を変更せずに新しい
qbpp::Exprオブジェクトを返します。 - メンバ関数:
qbpp::Exprクラスのメンバ関数です。 多くの場合、呼び出し元のオブジェクトを更新し、結果のqbpp::Exprも返します。
例: sqr()
sqr()関数は式の二乗を計算し、両方の形式で利用できます:
sqr(f)（グローバル）: fを変更せずにfの二乗を返しますf.sqr()（メンバ）: fをその二乗に更新し、更新された式を返します
代入演算子: =
左辺はqbpp::Exprオブジェクトでなければなりません。 右辺はExprTypeでなければならず、まずqbpp::Exprに変換されます。 変換された式が左辺に代入されます。
二項演算子: +, -, *
これらの演算子はグローバル関数として定義されています。 2つのExprTypeオペランドを取り、結果を計算して返します。 少なくとも1つのオペランドがqbpp::Exprの場合、結果は常にqbpp::Exprになります。 どちらのオペランドもqbpp::Exprでない場合、結果はqbpp::Termになることがあります。
例
qbpp::Var型の変数xの場合:
2 + x:qbpp::Expr2 * x:qbpp::Term
複合代入演算子: +=, -=, *=
これらの演算子はメンバ関数として定義されています。 左辺はqbpp::Exprでなければなりません。 右辺のオペランドを使用して指定された演算が適用されます。 左辺の式がその場で更新されます。
除算/と複合除算/=
除算演算子/はグローバル関数として定義されています。
非整数のExprTypeオペランドを被除数として、整数オペランドを除数として取り、商をqbpp::Exprとして返します。
被除数の式は除数で割り切れなければなりません。つまり、 式内の整数定数項とすべての整数係数が除数で割り切れる必要があります。
複合除算演算子/=はメンバ関数として定義されています。
- 左辺は
qbpp::Exprでなければなりません。 - 右辺は整数でなければなりません。
同じ割り切れ条件が適用され、除算はその場で実行され、左辺の式が更新されます。
比較（等値）: ==
等値比較演算子==は以下を取ります:
- 左辺に非整数の
ExprType - 右辺に整数
等値制約が満たされたときに最小値0となる式を返します。 より具体的には、非整数のExprTypeオブジェクトfと整数nに対して、演算子はqbpp::sqr(f-n)を返します。
返されたオブジェクトgについて:
gは制約式qbpp::sqr(f - n)を表し、g.body()は基礎となる式fを返します。
制約式の qbpp::Expr
ここで g は制約式の qbpp::Expr（penalty + body のメタデータを持つ qbpp::Expr）です。 g.body() を呼ぶと、関連付けられた基礎となる qbpp::Expr オブジェクトが返されます。
比較（範囲比較）: <= <=
範囲比較演算子は次の形式で記述されます:
l <= f <= u
ここで:
fは非整数のExprType、lとuは整数です。
この演算子は、範囲制約が満たされたときに最小値0となる式を返します。
より具体的には、単位間隔を持つ補助整数変数aが範囲[l,u-1]の値を取るように暗黙的に導入され、演算子は以下を返します:
(f - a)(f - (a + 1))
返された制約式 qbpp::Expr オブジェクトgについて:
gは制約式(f - a)(f - (a + 1))を表し、g.body()は基礎となる式fを返します。
片側比較: <=, >=
非整数 ExprType f と整数 n について、片側制約演算子が用意されています:
f <= n // f.neg_sum() <= f <= n と等価
f >= n // n <= f <= f.pos_sum() と等価
それぞれ片側制約が満たされたときに最小値 0 となる制約式を返します。 省略された側の境界は内部で f.neg_sum()（f の最小可能値）または f.pos_sum()（f の最大可能値）に設定されるので、補助整数変数の範囲は要素が取りうる範囲ぴったりに収まります。
単独片側演算子と qbpp::inf を用いたチェイン形は同一の制約式を生成します:
| 単独片側形 | 同等のチェイン形 |
|---|---|
f <= n | -qbpp::inf <= f <= n |
f >= n | n <= f <= +qbpp::inf |
単独片側形が推奨記法です。チェイン形は無限境界を明示したい場合 (テンプレートコード等) のために残されています。
注意 片側制約は必ず 式を左辺に置いて 書きます。
n >= exprはコンパイルエラー (= deleteで明示的に禁止、エラーメッセージは “use of deleted function”)。 逆向きのn <= exprは単独ではエラーにできません (チェインn <= expr <= mの 開始部と同じトークン列のため)。ただしstd::pairを返すので+,*,sqr(),simplify_*()等を一切持たず、その後の操作で必ずコンパイルエラーになります。
配列 arr に対しても要素ごとに arr <= n / arr >= n が動作し、各要素の pos_sum() / neg_sum() を自動的に他側境界とします (補助変数のサイズが要素ごとに最小化されます)。
二乗関数: sqr()
qbpp::Exprオブジェクトfに対して:
qbpp::sqr(f)（グローバル関数）: 式f * fを返します。 引数fは非整数のExprTypeオブジェクトでもかまいません。f.sqr()（メンバ関数）:fをその場でf * fに置き換え、更新された式を返します。
最大公約数関数gcd()
グローバル関数gcd()はqbpp::Exprオブジェクトを引数として取り、すべての整数係数と整数定数項の最大公約数（GCD）を返します。
与えられたqbpp::Exprオブジェクトは結果のGCDで割り切れるため、すべての整数係数と整数定数項をGCDで除算しても、式の構造や最適解は変わりません。
簡約化関数: simplify(), simplify_as_binary(), simplify_as_spin()
qbpp::Exprオブジェクトfに対して、メンバ関数f.simplify()は以下の操作をその場で実行します:
- 各項内の変数を一意な変数IDに従ってソート
- 重複する項をマージ
- 項を以下の規則でソート:
- 低次の項が先に現れる
- 同じ次数の項は辞書順に並べる
グローバル関数qbpp::simplify(f)はfを変更せずに同じ操作を実行します。
バイナリとスピンの簡約化
簡約化関数の2つの特殊なバリアントが提供されています:
simplify_as_binary(): すべての変数がバイナリ値$\lbrace 0,1\rbrace$を取ることを仮定して簡約化が実行されます。 恒等式$x^2=x$がすべての変数$x$に適用されます。simplify_as_spin()すべての変数がスピン値$\lbrace -1,+1\rbrace$を取ることを仮定して簡約化が実行されます。 恒等式$x^2=1$がすべての変数$x$に適用されます。
両方のバリアントはメンバ関数とグローバル関数として利用できます:
- メンバ関数: その場で簡約化を実行し、
fを更新します。f.simplify_as_binary()f.simplify_as_spin()
- グローバル関数: fを変更せずに簡約化された式を返します。
qbpp::simplify_as_binary(f)qbpp::simplify_as_spin(f)
評価関数
qbpp::MapListオブジェクトは、qbpp::Varオブジェクトと整数のペアのリストを格納します。 各ペアは変数から整数値へのマッピングを定義します。
qbpp::Exprオブジェクトfとqbpp::MapListオブジェクトmlに対して、評価関数f(ml)はmlで指定された変数割り当ての下でfの値を評価し、結果の整数値を返します。
fに現れるすべての変数は、mlに対応するマッピングが定義されていなければなりません。
置換関数: replace()
qbpp::MapListオブジェクトには、qbpp::VarオブジェクトとExprTypeオブジェクトのペアも含めることができます。 このようなペアは変数から式へのマッピングを定義します。
qbpp::Exprオブジェクトfとqbpp::MapListオブジェクトmlに対して:
qbpp::replace(f, ml):fを変更せずに、mlのマッピングに従ってf内の変数を置換した新しいqbpp::Exprオブジェクトを返します。f.replace(ml):mlのマッピングに従ってf内の変数をその場で置換し、結果のqbpp::Exprオブジェクトを返します。
バイナリ/スピン変換関数: spin_to_binary(), binary_to_spin()
xをバイナリ変数、sをスピン変数とします。 x = 1であるとき、かつそのときに限りs = 1であると仮定します。 この仮定の下で、以下の関係が成り立ちます:
$f(s)$をスピン変数$s$の関数とします。 このとき、関数$g(x)=f(2x-1)$は上記の関係の下で同じ値を与えるバイナリ変数$x$の関数です。
spin_to_binary()関数はこの関係を使用して、スピン変数の関数を表すqbpp::Exprオブジェクトをバイナリ変数の関数を表す等価なqbpp::Exprオブジェクトに変換します。 具体的には、f内のすべてのスピン変数sを2 * s - 1に置換します。
qbpp::spin_to_binary(f):f内のすべてのスピン変数sを2 * s - 1に置換した新しいqbpp::Exprオブジェクトを生成して返します。f.spin_to_binary():qbpp::spin_to_binary(f)を使用してfをその場で更新し、更新された式を返します。
同様に、binary_to_spin()関数はf内のすべてのバイナリ変数xを(x + 1) / 2に置換します。 結果の式には非整数の係数が含まれる場合があります。 そのため、すべての係数が整数になるように、式全体が$2^d$（$d$はすべての項の最大次数）で乗算されます。
spin_to_binary()と同様に、binary_to_spin()にもグローバル関数とメンバ関数の両方のバリアントが提供されています。
タプルインデックス a(...)
Array の operator() で Python タプルインデックス風のサブ配列取得ができます。各引数は軸ごとに以下のいずれか:
| 引数 | 意味 | 次元変化 |
|---|---|---|
整数 i | その軸を i に固定 | 軸が削除される |
qbpp::all | 全範囲 : | 軸を保持 |
qbpp::slice(from, to) | 範囲 [from, to) | 軸を保持 |
qbpp::end / qbpp::end - n | 軸サイズから計算される位置 | 固定または範囲端 |
指定しなかった末尾の軸は自動的に qbpp::all とみなされます。
出力は C ABI view を 1 回呼び出して構築するため、結果サイズに比例した O(output_size) のコピーコストになります。
使用例
// 2D 配列
auto x = qbpp::var("x", 3, 4);
auto row0 = x(0); // axis 0 を 0 に固定 → 1D (4,)
auto col2 = x(qbpp::all, 2); // axis 1 を 2 に固定 → 1D (3,)
auto sub = x(qbpp::slice(0, 2), qbpp::slice(1, 3)); // 2D (2, 2)
// 3D 配列
auto y = qbpp::var("y", 2, 3, 4);
auto s = y(1, qbpp::all, 3); // axis 0,2 を固定 → 1D (3,)
auto v = y(1, 2, 3); // 全軸固定 → Var
// end キーワード（MATLAB 風）
auto last5 = x(qbpp::slice(qbpp::end - 5, qbpp::end)); // 末尾 5 要素
auto mid = x(qbpp::all, qbpp::slice(1, qbpp::end - 1)); // 内側のみ
詳細と例については スライス関数と連結関数 を参照してください。
連結関数: concat()
連結関数は配列の結合やスカラーの追加・先頭追加を行います。
配列 + 配列
qbpp::concat(a, b): 同じ型の2つの配列を最外次元に沿って連結します。
スカラー + 配列 / 配列 + スカラー
qbpp::concat(scalar, v): 配列の先頭にスカラーを追加します。qbpp::concat(v, scalar): 配列の末尾にスカラーを追加します。
スカラーはqbpp::Exprに暗黙的に変換されます。
2次元の次元指定付き連結
qbpp::concat(a, b, dim): 2つの2次元配列を指定した次元に沿って連結します。dim=0: 行方向の連結（行を追加）dim=1: 列方向の連結（列を追加。両方の行数が同じである必要があります）
例: 境界差分
auto x = qbpp::var("x", 4);
auto diff = qbpp::concat(1, x) - qbpp::concat(x, 0);
// diff = {1-x[0], x[0]-x[1], x[1]-x[2], x[2]-x[3], x[3]-0}
Term メンバ関数
以下の qbpp::Term のメンバ関数は、項の内部構造への読み取り専用アクセスを提供します。
| 式 | 戻り値の型 | 説明 |
|---|---|---|
t.coeff() | coeff_t | 係数を返す |
t.degree() | uint32_t | 次数（変数の数）を返す |
t.var(i) | qbpp::Var | i 番目の変数を返す |
t.has(v) | bool | Var v が項に含まれていれば true を返す |
例
auto x = qbpp::var("x");
auto y = qbpp::var("y");
auto z = qbpp::var("z");
qbpp::Term t = 3 * x * y;
t.coeff(); // 3
t.degree(); // 2
t.var(0); // x
t.var(1); // y
t.has(x); // true
t.has(z); // false
Expr メンバ関数
以下の qbpp::Expr のメンバ関数は、式の内部構造への読み取り専用アクセスを提供します。
| 式 | 戻り値の型 | 説明 |
|---|---|---|
f.constant | energy_t | 定数項を返す |
f.term_count() | size_t | 項の数を返す（定数項を除く） |
f.term_count(d) | size_t | 次数 d の項の数を返す |
f.term(i) | qbpp::Term | i 番目の項のコピーを返す |
f.max_degree | uint32_t | すべての項の最大次数を返す |
f.has(v) | bool | Var v が式に含まれていれば true を返す |
f.has(vi) | bool | 整数変数 vi のすべての変数が式に含まれていれば true を返す |
例
auto x = qbpp::var("x");
auto y = qbpp::var("y");
qbpp::Expr f = qbpp::simplify(3 * x + 2 * x * y + 5);
// f = 5 + 3*x + 2*x*y
f.constant; // 5
f.term_count(); // 2
f.term(0); // 3*x
f.term(1); // 2*x*y
f.term(1).coeff(); // 2
f.term(1).var(0); // x
f.term(1).var(1); // y
f.max_degree; // 2
f.has(x); // true
f.has(y); // true