アルゴリズムの設計

記号は前節と同じとする。簡単な考察により $\emptyset=\intersection_{B \in {\cal B}} B$かつ$E=\union_{B \in {\cal B}} B$ の場合が本質的であり、それ以外の場合はこの条件をみたすマトロイドを用いて容易に構成できることがわかる。以下、この条件をみたすマトロイドを数え上げるためのアルゴリズムの設計方針を述べる。上の仮定と基の公理の1つによって、任意の基$B$とその任意の元$e$に対して、$e$を$B$以外のある元に置き換えて得られる基が存在し、また全ての基はこのような1個だけの元の置き換えを繰り返して得られる。

そこで各基$B$に対して、「1個だけの元の置き換え」によって得られる基を特別視して、次のような量を定める。

\begin{eqnarray*} \deg B & := & |\{B' \in {\cal B}; |B \setminus B'| = 1\}|,\\ \deg_{e} B & := & |\{B' \in {\cal B}; B \setminus B' = \{ e \}\}| \textop{for}e \in B,\\ \deg^{-}_{e} B & := & |\{B' \in {\cal B}; B'\setminus B = \{ e \}\}| \textop{for}e \not \in B. \end{eqnarray*}

同型なマトロイドをできるだけ生成しないように、以下のような制限を設ける (そうしても一般性を失わない)。

$\deg$が最大の基は、$B_{0} = \{0,1,\ldots,r-1\}$.
$\deg_{0} B_{0} \ge \deg_{1} B_{0} \ge \ldots \ge \deg_{r-1} B_{0} > 0$.
$\deg^{-}_{r} B_{0} \ge \deg^{-}_{r+1}B_{0} \ge \ldots \ge \deg^{-}_{m-1}B_{0}$.

このようにすると、 ($\deg_{0} B_{0},\ldots,\deg_{r-1}B_{0}$)と($\deg^{-}_{r}B_{0},\ldots,\deg^{-}_{m-1}B_{0}$)が、 $\deg B_{0}$の分割になっていることに注意する。

そこで、$\deg B_{0}$の$r$個の正整数への分割をすべて求め、その各々の場合について、 $B_{0}$から「1個だけの元の置き換え」により得られる集合を上の規則をみたす様に構成する。以下新しく得られた基(の候補)の各々に対して、$\deg$が$\deg B_{0}$を超えないように注意しつつ、「1個だけの元の置き換え」を再帰的に実行して行くことにより、すべてのマトロイドを数え上げる。