数理解析研究所講究録 1325 巻 2003 年 63-68

63

自然数の組成の O(1) 時間生成について
三河賢治 (Kenji MIKAWA)

仙波一郎 (Ichiro SEMI3A)

茨城大学総合情報処理センター

茨城大学工学部情報工学科

rnikawa@mx.ibaraki.ac.jp

isemba@cis.ibaraki.ac.jp

あらまし

個の和囚子に分割する問題は, 次式 $a_{1}>\cdots>a,|$ と $a_{1}+\cdots+a_{r}=n$ を満を求める問題である. 本論文で扱う間雇は, 条件 $a1>’\cdot\cdot>a,$ . を省いて, 順序を考慮した自然数の分割について考える. 順序を考慮した自然数の分割は, 自然数の組成と呼ばれる.と Meadows により. 最大の和因子がであるような自然数の組成の個数は段フィボナッチ数列に一致することが証明された. 本論文では, 自然数の組成をーっ
自然数 をたす文字列$\# l$$r$$a_{1}a_{2}\ldots a_{\mathrm{r}}$$\mathrm{G}_{1}\cdot \mathrm{i}\mathrm{m}\mathrm{a}1\mathrm{d}\mathrm{i}$$k^{n}$$k$

当たり $O(1)$ 時間で生成するアルゴリズムを提案する.

キーワード :

1

自然数の組成,$k$段フィボナッチ数列, グレイコード, 逐次生成, 組合せアルゴリズム

まえがき
フィボナッチ数列を拡張した’$f(n, k)—$01$k$

段フィボナッチ数列 $f(n, k)$ は, 境界条件 $f(0_{:}k)=1$ として,$k=0$ のとき.

$\sum_{=1}^{k}\dot{.}$$k=1$ のとき
$j(\text{へ}-i_{i}k)$$k\leqq n$.

$\backslash f(n_{j}r\iota)$$\mathrm{A}^{-}$$>’\iota$のときのときのように再帰的に定義される. フィボナッチ数列は 2 段フィボナッチ数列と考えることができる.
自然数の分割とは, 自然数 を適当な自然数の和に表現する問題である. 例えば, 5 の分割は
$n$1+1+1+1+1,2+1+1+1,2+2+1,3+1+1,3+2,4+1,5 の 7 通り考えられる. 自然数の分割の個数を分割数と呼ぶ. この例では, 5 の分割数は 7 になる. 和を構成する数字を和因子と呼び, 最大の和因子を指定して, 自然数の分割を考えることもできる.
例えば, 最大の和因子を 3 とすると, 5 の分穎 H よ 1+1+1+1+1,2+1+1+1,2+2+1,3+1+1,3+2 の 5 通$\mathrm{n}$り考えられる. 従って, この場合の分割数は 5 となる. 自然数を幾っがの和因子に分解する問題では, 3+2 と 2+3 は等しい分割とする見方と異なる分割とする見方の二っの考え方があるが, 前者を自然数の分割, 後者を自然数の組成と呼んで明確に区別される.
本論文では, 最大の和因子が であるような自然数 のすべての組成を生成するアルゴリズ\Deltaを提案する. 文字列を一定の順序で並べたものをリストと呼ぶことがあるが, 以下, 本論文でも組$k$$r\iota$

成を並べたものをリストと呼ぶことにする. Savage [5] は, 自然数の分割におけるグレイコードを次のように定義し, これを満たす自然数 の分割を生成する手法を提案した.
$r\iota$

定義 Ll 自然数割から次式$n$の分割のリス]. $A$ につぃて,$i$番目の自然数の分割が $i-1$ 番目の自然数の分

64

図 1

列挙木 $T(6.3)$(1) 和因子の値を 1 増やし, 1 より大きい和因子の値を 1 減らす,(2) 和因子の値を 1 増やし, 和因子 ‘1’ を取り除く.
(3) 1 より大きい和因子の値を 1 減らし, 和因子 ‘1’ を新しく加える,の何れかから得られるとき,$A$はグレイコードである.

近年, Grirnaldi と Meadows [3] は, 自然数の組成の分割数が 段フィボナッチ数列に一致することを証明した. 本論文では, 上記で定義されたグレイコードの性質を満たすような組成のリスト$k$を生成するアルゴリズムを提案する.

2

生成アルゴリズ A
リストの表記法を定義しよう.
{固の文字と表す. リスト , 記号 に対して, . .

始めに,
イ]

$/\mathrm{J}\Pi$$\eta_{1}’|$

$7l$

$L$

$\langle l_{1}, l_{)}.., \ldots, l_{n}\rangle$$x$$x$$L$$l$,,$l_{n}$$l_{\underline{9}},$$\ldots,$である.

$7l$$\#_{\mathrm{D}}^{\pm}$個の文字列する. 例えば $L=\langle 21,31\rangle,$$l_{1}.l_{2},$$l_{\eta}$$\ldots,$からなるリスト$L’=\langle 43,53\rangle$のとき,$L=\langle l_{1}, l_{\underline{)}}., \ldots, l_{n}\rangle$を示す first(L) と末尾の文字 F 火, を示す last(L) を定義する. また,並べたリスト$\overline{L}=\langle l,‘’\ldots, \mathit{1}_{2}, l_{1}\rangle$$\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}(\overline{L})=\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(L)$を定義し,$\overline{L}$を$L$

リスト $L(n, k)$ は,$2^{3}1^{2}$

を $L=$$L’$に対して,$x$を$L\mathrm{o}L’$$L\circ L’=\langle 21,31,43,53)$に対して, 先頭の文字列
リスト$L$の反 .1 云と呼ぶ. 明らがにが成立する. 次に, 組或の表記法を定義する. 和因子と表記する. 例えば組成 22211 ならば$L$

は $L$ に含まれる各文字列の先頭にする. 例えば $L=\langle 21,31\rangle$ のとき, 4 $\cdot L=\langle 421,431$ ) である. リスト $L,$

は二つのリストを連$\alpha^{b}$からなるリスト$a$. の文字列を逆順に$\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\overline{L})=$,が$l_{1}$$b$last(L),個連続するとき,である.

) を基底として,$L(n, 0)=\lambda_{\mathrm{I}}L(n, 1)=\langle 1^{n}$$1<k\leqq n$につ$1^{\mathrm{a}}\text{て}$,$L(7l_{i}k)=1\cdot L(n-1, k)02\cdot\overline{L(n-2,k)}$$\circ 3\cdot L(\tau\iota-3, k)\circ 4\cdot\overline{L(n-4,k.)}$$\circ\cdot \mathrm{J}Lr.(n-5, k)\circ\cdots$個の部分リストの連結として定義する. このとき, $L(r\iota, k)$ の先頭の部分リストが反転個の部分リストを交互に反転する. すなわち偶数番目の部分リストは反転し, 奇数番目の部分リストは反転しない. 一方, $k>n$ について,のように$J_{i}$しないように

.

$k.$

$L(?l, k)=L(n, n)$のように定義する. 例として, リスト $L(6,3)$ の構造を表すグラフ $T(n, k)$ を図 1 に示す. このようなグラフは列挙木と呼ばれ, $T(n, k)$ の根から葉までの経路が $L(n, k)$ の組成に対応する.

65

組成

$a_{1}a_{\sim^{)}}.\ldots a.,$. について,の選び方は 1, 2, . . . ,$a_{1}$$k$の. 通りある.

$k$

ここで $a_{1}=i$ に固定すると, 文字列は部分リスト $L(n-i, k)$ の要素と考えることができる. $a_{1}=i$ を満たす組成を要素とする $L(n, k)$ の部分リスト $i\cdot L(n-i$ , 幻について, a2 以下の文字についても順に値を特$a_{\underline{9}}\ldots a_{r}$定していく. 末尾の文字 . の値を特定したとき, 即ち $n=0$ のとき, $L(n, k)$ の要素が–っ決定する. 従って, リスト $L(n, k)$ は, 最大の和因子が であるような 然数 の組成を系統的に並$a_{?}$$k$$.\text{自}$

$n$

べている.

補題 21 リスト $L(n, k)$ の先頭の文字列について,first $(L(n, k))=1’\iota$が成立し, 末尾の文字列について,$k^{\lfloor\cdot/k\rfloor}’.s$l 邸 t(L(n, $k)$ ) $=\{$.

$k1^{n-\mathrm{A}}$$k$$k$が成立する. だだし, $s=?l$ luodが奇数のときが偶数のとき$k$である.

定理 21 リスト $L(n, k)$ はグレイコードである.
(証明)に関する帰納法で証明する. 明らかにについて定理は成立する. $n\leqq m$ について定理は成立すると仮定し, $n=m+1$ につぃて考える. 奇数 につぃて, $L(m+1, k)$ を$\prime n=1$

$n$

$i$

$L(?1\iota+1, k)=1\cdot L(m, k)\circ\cdots$$\circ i-1\cdot\overline{L(m-i+2,k.)}$$\circ i\cdot L(m-i+1, k)$$\mathrm{o}i+1\cdot\overline{L(m-i,k-)}\circ\cdots${ 部分リストの連結で表す. 帰納法の仮定により部分リストの内部で定理は成立しているので, 各部分リストの境界について定理を示せばよい. 補題 2.1 で示してぃるように,のバリティによって部分リス の末尾の文字列の振る舞いが異なる. そこで,が奇数である場合と偶数である場合の二つの場合に分けて考えてぃく.
1) が奇数である場合. 始めに, 部分リス加 –1の末尾の文字列と部分リスト $i\cdot L(m-i+1, k)$ の先頭の文字列との境界で定理は成立することを示す. 補題 2.1 より, 部
分リス加 –1 $\cdot\overline{L(m-i+2,k.)}$ の末尾の文字列は,のように$)$$\wedge,\cdot$$k$$|\backslash$$\langle$

$k$

$k$

$\cdot\overline{L(?n-i+2,k^{\kappa})}$last(.i–l $\cdot\overline{L(n\iota-i+2,k.)}$ )$=\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{s}\iota(i-1\cdot L(m-i+2, k))$,$=i-11^{n1-\mathrm{i}+}.-$

である. 一方, 部分リスト $i,$ $L(rn-i+1, k)$ の先頭の文字列は,$\mathrm{f}\dot{\mathrm{u}}\cdot \mathrm{s}\mathrm{c}(i\cdot L(?t\cdot\iota-i+1, k))=i1^{rn-i+1}$である. 二つの文字列を比較すると, 部分リス加$(rn-\primei+2, k)$ の末尾の文字列の先頭の文字-l.L–の値を 1 増やし, $m-i+3$ 番目の和因子 ’1’ を取り除くことにょって, 部分リス加. $L(rn-i+1, k)$の先頭の文字列を得る. 従って, 定義 1.1 の (2) を満たしてぃる.
次に, 部分リスト $i\cdot L(m-i+1, k,)|$ の末尾の文字列と部分リス加 $+1\cdot\overline{L(m-i,k)}$ の先頭の文字列との境界で定理は成立することを示す. 補題 2.1 より, 部分リス加. $L(m-i+1, k)$ の末尾の文字列は,last $(i\cdot L(l\tau\iota-i+1, k))=ik^{[m-i+1/k\rfloor_{S}}$66

図 2である.

$\cdot$

節点$v$と定義された節点との関係

一方, 部分リス $|\backslash i+1\cdot L(7n-i, k)$ の先頭の文字列は,$\mathrm{f}\mathrm{f}\mathrm{i}\cdot \mathrm{s}\mathrm{r}(i+\mathrm{I}\overline{L(m-i,k..)})=1\mathrm{a}\mathrm{s}\mathrm{t}(i+1\cdot L(m-i, \ ))$$=i+1k^{\lfloor m-:/k\rfloor}.s’$である.

$s$の取りうる{直は$\lambda,$$1,2_{\backslash }\ldots,$$k-1$ なので,$s=\lambda,$$s=1,$ $s=2,$$\ldots,$$k-1$ の三つの場合に分けて両者を比較しよう. 和因子 ‘ ’ の個数はそれぞれ $t=[m-i+1/k^{\wedge}$」, $t’=[m-i/k$ 」 で$k$ある.の場合. $t’=t-1,$ $s’=k-1$ が成立するので, 両者の文字列長は等しく, 先頭と(IA)末尾の文字だけが異なっている. 従って, 定義 1.1 の (1) を満たす.
(1B) $s=1$ の場合. $t’=t,$ $s’=\lambda$ が成立する. 従って, 定義 1.1 の (2) を満たす.
$k-1$ o) 場合. $t’=t,$ $s’=s-1$ が成立する. 従って, 定義 1.1 の (1) を満たす.
(1C) $s=2,$以上,が奇数である場合, リスト $L(n, k.)$ はグレイコードであることが確かめられた.
$s=\lambda$$\ldots,$$k$

同様に,$k$が偶数である場合も,

3

時間アルゴリズ\Delta$O(1)$

リスト $L(n, k)$ がグレイコードであることを確かめることがでの場合も定理は成立する. 故に, 定理は証明された.

きるので,$n=\iota n+1$口

列挙木は組合せ的な集合の要素の構造を表し, 計算機上で実現するデータ構造に適している. また, 列挙木上の各要素を効率良く生成するアルゴリズムは文献 $[6, 4]$ に詳しく述べられている. 本
節では, これらの文献に習い上の組成を $0(1)$ 時間で生成するアルゴリズ\Delta を提案する.
始めに, 文献 [4] による $O(1)$ 時間アルゴリズムの戦略について述べる. 列挙木の根か$a(i)$$a(0)$として, 根ら葉までの経路で深さ垣こ位置する節点をを除いた節点の系列 $a(1)\ldots a(r)$ ,.
が組成である. 根 $a(0)$ に接続する 個の子 1, 2, . . . , の中から任意に $1\leqq j’<k$ を選び,部分木 $T(n-j, k.)$ と $T(r\iota-j’-1, k)$ の境界に面する二つの組成について考える. 部分木 $T(n-j, k)$の最右端の経路に対応する組成を $a=a(1)\ldots a(r)$ , 部分木 $T(n-j-1, k)$ の最左端の節点の経路に対応する組成を $a=a’(1)\ldots a’(r’)$ とする. 組成の次列は, 定理 2,1 の証明の中で示された通り,の奇偶によって求めることができる. 即ち,が偶数である場合, 補題 2.1 より,$T(\uparrow\iota, h.)$$T(?\mathit{1}, k)$$\uparrow$$\leqq n$.

$k$$k^{n}$$a$$a(i)=\{$$a$$j$$\mathrm{j}$$j$$i=1$ のとき

1$i=2_{:},$.

)$r\mathit{0}$$.,$$k\mathrm{g}$と$a’(i)=\{$$j+1$$i=1$ のとき

1$i=2,$$\ldots,$$r-1$ のとき

67

output $a(1)\ldots a(.’\iota)j$$i:=d(.ll);r:=nj$
do begin
A3whileA42 文字 $a(i)$ とその池を変換して, 次列を生成する ;outputA5
Al$\Lambda^{\underline{\eta}}$$i>\mathrm{O}$$a(1)\ldots a(r)\mathrm{i}$A6$u(i):=\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}(a(i))j$A7A8A9A1O$r:=a(i)$ を根とする部分木の最 . 端の菓の深さ;
lf $a(i)=$ 末弟の節詰 then begin

Allend;$/_{-|}^{--}$$\backslash \mathrm{i}$$u(i):=\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}(\mathrm{a}(\mathrm{i}))j$$d(i):=d(i-1)jd(i-1):=i-1$$i:=d(r)jd(t):=r$A12
A13endj

生成アルゴリズ\Delta

図 3が成立するので, $a’(1)=a(1)+1,$ $r’=r-1$ によって組成 $a$ を得る. 一方,($\iota’(1)=n(1)+1$$j$が奇数である場合,として, $a(r)=1$ ならば $r’=\mathrm{r}-1,$ $a(r)>1$ ならば $r’=r$ かつ $a’(r’)=a(r)-1$を得る. 列挙木 $T(n, k)$ は再帰的に定義されるので, 上記の交換規則は $T(n, k)$の内部についても帰納的に言える. 組成の文字列長の差による変換も 1 文字として考えると, どの組成も 2 文字だけ相異なるように並んでいる. ここで, ある組成から次列を生成するときに変換される文字の中で最も先頭に近い文字に注目する. 文献 [4] では, このような文字を列挙木の節点になぞらえて生成節点と呼び, 次のように定義した. $T(n, k)$ の節点を行きがけ順にたどるときの節点の系列を考える. このとき任意の節点 について,より後にたどられる節点の中で に最も近くかつ $T(n, k)$ の根から等しい深さの節点を right(v) と表ず. また任意の 2 節点 $v,$にと $v’$ から最も近い共通の先祖をついて,とを結ぶ経路 に位置すとする. このとき,るの子を gen(v, $v’$ ) と表し, これを生成節点と呼ぶ. 特に gell(v, right(v)) を gen(v) と表す.
によって組成

$a$

$v$

$v$

$.\mathit{0}$

$v’$

$v$

$w$

$-\vdash_{arrow}$

$w$

$v$

$w$

節点
節点$v$と, 節点 1’ に関係する gen(v), right(v) との関係を図 2 に示す. また $T(n, k.)$ の深さ$‘\iota(i)$$i$のについて. 生成節点 gen(a(i)) の深さを記憶する配列 $d(i)$ を用意する. 便宜的であるが( l). . . $a(r)$ に文 で gen(a(i)) $=a(0)$ とする.
$T(n, k.)$ 上の組成を生成するアルゴリズ\Delta を図 3 に示す. アルゴリズムの基本動作は次の通りである. $T(n, k)$ の根 に接続する 個の節点. に対して, を根とする部分木の先頭の葉を , 末尾の葉をとする (図 4 参照). 生成アルゴリズムでは, $T(n, k)$ の先頭の葉から順々に葉を移動し, 末尾の葉#こ到達するとき, . から { に移動してアルゴリズ\Lambdaを終了する. この動作を基本として,に接続する先頭の部分木 $T(n-1, k)$ について, 先頭の葉$d(0)=0$ として, $T(n, k)$ の最右端の節点の系

$k$

$v$

$x_{i}$$l$$\gamma_{1}y\downarrow a$$v_{1},$$\ldots,$$\text{し}$$T(\uparrow\iota-i, k)$$v_{i}$$v_{k}$$y_{i}$$x_{1}$$y_{k}$$j$$y_{k}$$v$に到達するとき, 部分木の根に移動する. これで $T(n-1, k)$ の節点の探索は終了したので, 次に隣接する部分木 $T(n-2, k)$ の根に移動し, 先頭の葉がら同様の移動を繰り返す. これを末尾の部分木 $T(\uparrow l-k, k)$ まで繰り返すのだが, $k-1$ 番目の部分木 $T(n-k+1, k)$ の節点の探索を終了したとき, 即ちに移動するとき, $d(1)$ のから$d(0)$値をの値に変更し, $d(0)$ の値を 0 に戻す. そしてがら . に移動し, 先頭の葉 . が$X\downarrow$から始めて末尾の葉$y_{1}$$v_{1}$$x_{2}$$v_{2}$$y_{k-1}$$v_{k-1}$$v_{k-1}$$x_{h}$$v_{k}$

ら $T(n-k, k)$ の節点の移動を始める.
$T(./\iota-k, k)$ の内部についても, 上で述べた節点の移動を行うので, $T(n-k, k)$ の根. と末尾の
葉 . を結ぶ経路上の深さ の節点に到達するとき, d(力の値を $d(j-1)$ の値に変更し, $d(j-1)$の値を $j-1$ に戻す. $T(n-k, k)$ の末尾の葉は深さ の節点であると仮定すると,の値は連鎖的に $d(0)$ の値に等しくなるので,を参照するとの深さ 0 を得に到達するとき
る. 以上, 列挙木 $T(n-k, k)$ の節点の移動と, $O(1)$ 時間の計算量で末尾の葉から根 に移動する{ff.4^‘理を述べた. $T(n, k)$ の内部の部分木についても帰納的に同様の議論が成立する. 従って,
$v_{k}$$y\mathrm{t}$$j$$y_{h}$$y_{k}$$d(7^{\cdot})$$r$$d(?\cdot)$$v$$y_{k}$

$v$

68

図 4

生成アルゴリズ$\text{ム}$$T(n, k.)$の巡回方法

は $O(1)$ 時間の計算量で各生成節点を計算している.

次に, 生成アルゴリズムの A7 で計算される組或の文字列長につぃて考えてぃく.

組成を $a=a(1)$ . .
長は,$\mathrm{u}(.i-1)$$T(n, k)$bの$a(r)$ , その次列を $a=a’(1)\ldots a’(r’)$ , 生成節点を $a(i)$ とする. 組成の文字列を根とする部分木が反転している場合と, 反転していない場合に分けて考える必要$,$がある. $a(i-1)$ を根とする部分木が反転していない場合, 即ち $a(i)<a’(i)$ の場合は, 定理 21の証明の中で示された通り,$r’.=\{$$r-1$$a(r)=1\mathit{0}\mathrm{J}\epsilon\epsilon$$a(r)>1$ のときが成立する. 一方, $a(i-1)$ を根とする部分木が反転してぃる場合, 即ち $a(i)>a’(i)$ の場合は,$a(r)=1$ のとき$r$$?.’=\{$$\}$. $+1$$a(i)$が奇数のとき, または $a(r\cdot)=k$ のときが成立する.
配列 の初期値は, 生成節点の定義から, $d(i)=i$ , $i=0,$の文字列は補題 2.1 で与えられる. 最後に次の定理を与える.
$d$定理 3.1 リスト$L(\uparrow\tau, k)$$\ldots,$$r\iota$である. また $L(n, k)$ の先頭の各組成を $0(1)$ 時間で生或することができる.

参考文献[1] M.
“A completeof whell generalized Tribonacci sequences can be avoided byadditive partitions,” Electl on. J. Courbiu.,,2000.
[2] 1. Dulnitriu,
generalizcd Tribonacci sequences aud additive pal.titions,” Discrete Math.,,,2000.
$\mathrm{D}\mathrm{e}\mathrm{v}\mathrm{e}1\mathrm{i}\mathrm{n}_{:}$$\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{g}\mathrm{o}\mathrm{l}\cdot \mathrm{i}\mathrm{z}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\cdot$$\mathrm{v}\mathrm{o}\mathrm{l}.7,$$\#\mathrm{R}\ulcorner 03$$u\mathrm{O}\mathrm{n}$$\mathrm{v}\mathrm{o}\mathrm{l}.219$$\mathrm{p}\mathrm{p}.65-83$[3] R. P. Grimaldi alld D. S. Meadows, “Compositions of integcrs,” Congre. Nuuter.,$\mathrm{v}\mathrm{o}\mathrm{l}.76\dot,$$\mathrm{p}\mathrm{p}.119-125$

1990.

,

[4] 三河賢治, 仙波一郎, “ フィボナッチ列の $O(1)$ 時間生成につぃて. ” 信学論, vOl.J85-D-I, no 2, pp.116-121,

2002.
[51 C. D. Savage, “Gray code sequences of partitions,” J. Algorithrns, vol.lO, pp.577-595, 1989.
T. Takaoka,
time algorithms for combinatOl.ial generation by tree traversal,”$‘:_{O(1)}$$[\mathrm{C})]$$\mathrm{v}\mathrm{o}\mathrm{l}.42,$$\mathrm{p}\mathrm{p}.400-408$,1999.

$\mathrm{C}_{\mathrm{o}\mathrm{n}1}\mathrm{p}\mathrm{u}\mathrm{r}$. J.,