この HOWTO 第2部では、高度にカスタマイズされた分割の生成を扱う。 第1部と同じように "from nzmath.combinatorial import *" してあることを仮定する。 次期 NZMATH もまもなく登場予定だが、待ちきれない人は前回と同じく mercurial リポジトリから直接クローンして試すことができる。
1. PartitionDriver
第1部では、partition_generator をいかに使いこなすかという課題に取り組んだ。 しかし、この方法は何かしら全単射を与えることができないならば、 無駄に多く生成してフィルタリングするという効率の悪い方法を採らざるを得ない。 より柔軟に条件付けた分割の生成には、PartitionDriver というクラスを使う。 正確には、必要に応じて PartitionDriver から継承したクラスを作成する。
まずは基本形から見ていこう。 partition_generator の呼び出しと同等のことは次のようにすれば良い。
>>> driver = PartitionDriver() >>> for partition in driver.generate(5): ... print partition ... (5,) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1) >>>
インスタンスを生成して、generate を呼び出すだけである。
generate は、拡張されることを考えて書かれたテンプレートメソッドである。 これからこの拡張を少しずつ学んでいくために、まずはそのコードを見ておこう。
def generate(self, *args):
"""
Generate all partitions of integer
Variable arguments *args will be used in inherited method.
"""
self.set_parameters(*args)
if not self.ispreconditioned():
raise StopIteration
while True:
while self.rest:
self.pull()
if not self.rest:
yield tuple(self.partition)
self.backtrack()
if self.shouldterminate():
break
self.push()
set_parameters, ispreconditioned などのメソッドを再定義することで 振る舞いを変えることができる。元々の振る舞いは以下の通りである。 (できれば実際のコードを参照して欲しい。)
- set_parameters:
- 一つの自然数を受け取り、self.rest に代入する。 self.partition を空リスト([])に初期化する。
- ispreconditioned:
- 常に True を返す。
- pull:
- self.rest から self.partition の最後の要素を超えない分だけ引き去り、 それを self.partition の最後に付け足す。self.partition が空のときは self.rest 全てを self.partition の1要素とする。
- backtrack:
- self.partition の最後に並ぶ 1 を全て取り去り、それらを合算したものを self.rest に代入する。
- shouldterminate:
- self.partition が空ならば True を返す。それ以外ならば False。
- push:
- self.partition の最後の要素から 1 を引き、self.rest に 1 を加える。
2. 奇数への分割, 再び
第1部の最後に、奇数への分割を扱った。いまそれをジェネレータ関数の形で書けば、
def partition_into_odd(n):
for m in range(n//2 + 1, n + 1):
for partition in partition_generator(n - m, 2*m - n):
yield tuple(2*x - 1 for x in partition_conjugate((2*m - n,) + partition))
となる。これは n の奇数への分割を次のように構成している。 m を (n/2, n] の中にある整数を動くものとし、m の最大がちょうど 2m-n になる分割の共役の各部分 x を 2x-1 に変換する。 見通しが良いとは言い難い。
それでは、PartitionDriver を継承して、奇数への分割を生成するようにしてみよう。 全ての数を使う代わりに、奇数だけを self.partition に収めるようにすれば良い。 要素を選んでいるのは pull と push なので、そこだけ変更する。
pull は self.rest から self.partition に足される部分を送り込む動作である。 デフォルトでは送り込めるだけ送り込む方針だが、ここでは奇数しか送り込んではいけない。 そこで、self.partition の最後の要素(これは奇数しか入っていない)よりも self.rest が大きければ self.partition の最後の要素と同じだけ、そうでなければ self.rest から取れる最大の奇数を self.partition に送り込むようにする。
一方の push は、次の分割の生成に移るために 1 でない最後の要素を減らす動作である。 ここでも、デフォルトでは 1 ずつ減らすが、これではせっかく奇数だった部分が偶数 になってしまうので、2 減らして奇数性を保つようにする。
最終的に、奇数への分割を生成するクラスはこうなる。
class OddPartitionDriver(PartitionDriver):
def __init__(self):
PartitionDriver.__init__(self)
def pull(self):
if self.partition and self.rest >= self.partition[-1]:
part = self.partition[-1]
elif self.rest % 2:
part = self.rest
else:
part = self.rest - 1
self.partition.append(part)
self.rest -= part
def push(self):
self.partition[-1] -= 2
self.rest += 2
コードの量は増えるが、やっていることは奇数を使って分割を作っていくという目的そのものに対応しているので、解り難くはないだろう。
3. そこそこ相異なる
全ての部分が相異なる分割は良く知られているが、ここではもう少し制限を緩めて、同じ大きさの部分は高々二つという分割を考えてみよう。
まずは pull を考えよう。 同じものを二つまでしか使えない、という制約を与えるためには、self.partition の 最後二つを見なければならない。 つまり、self.partition の最後の要素と、最後から二番目の要素が等しくなければ、 self.partition と同じだけ self.partition に送り込んでも良い。 二つが等しければ、大きくとも最後の要素より 1 小さい数しか送り込んではいけない。
def pull(self):
if len(self.partition) >= 2 and self.partition[-1] == self.partition[-2]:
maximum = self.partition[-1] - 1
elif self.partition:
maximum = self.partition[-1]
else:
maximum = 0
if self.rest >= maximum:
part = maximum
else:
part = self.rest
self.partition.append(part)
self.rest -= part
今度は backtrack も考えないといけない。 backtrack は要するに生成の様子を樹上に配置したとして分岐ノードまで巻き戻すという操作である。 デフォルトでは最後の 1 の並びだけを取り去るが、今考えているそこそこ相異なるものの生成では、たとえば (1, 1) の前が (2, 2) だったら、もはやそれ以上その並びから進むことはできないので、(2, 2) の部分も取り去らないといけない。 そうすると、単純に二つずつ並んでいたら取り除くということで良いように思ってしまうかもしれないが、残念ながら必要な条件はそれほど簡単ではない。 (4, 3, 2, 1, 1) という分割から進むことを考えてみると、まず (1, 1) を取り除くことになる。 ところが、次の 2 を崩すとすれば 1 が二つまでという制約に違反することになるから、2 も取り除かねばならない。 ところがところが、さらに次の 3 を崩すと、2 と 1 か 1 を三つ(この時点でアウト)にしないといけないので、結局 1 が二つまでという制約を満たすことができなくなる。 したがって、3 も取り除く。 この勢いだと 4 も取り除かなければいけなくなるかと思いきや、3 と 1 に分けた内の 1 を既にある 1 の一つと合わせて 2 にすれば、(3, 3, 2, 2, 1) にできるので、4 は取り除かない。 さて、この判断を実際に新しい分割を構成せずにしなければならないが、どのようにすれば良いのだろう。
1 から k までの和は k*(k+1)/2 である。 そこで、いくつかの数を分割から取り除いて残っている最後の(一番小さい)数を m としよう。 次の分割に移るには、m を小さくするしかないので、m と今までに取り除いた分の数 r の和を m-1 までの数のそれぞれの数が高々二つまでの和に直せないといけない。 つまり、m + r <= (m-1)*(m-1+1)/2*2 = m*(m-1) でなければここは分岐ノードではなく、m も取り除いてさらに上のノードまで巻き戻さなければならない。 逆に m + r <= m*(m-1) が成り立っていればどうだろう。 等号が成り立つならば 1 から m-1 まで二つずつ埋められることは明らかである。 不等号であれば、そこからいくつか抜けばいいので、少なくとも一通りは条件に合う分割が得られる。
まとめよう。 まず 1,2,2,3,3 または 1,1,2,2 のように下から順番に埋まっている部分を取り除いて足し合わせ r とする。 さらに残った部分の内最小のものを m として、m + r > m*(m-1) である間その m を取り除き続ける(取り除いたら r に加える)。 つまり、こうなる。
def backtrack(self):
if len(self.partition) >= 2 and self.partition[-1] == 1:
if self.partition[-2] == 1:
i = 1
else:
self.rest += self.partition.pop()
i = 2
while len(self.partition) >= 2 and self.partition[-2] == i:
self.rest += self.partition.pop()
self.rest += self.partition.pop()
i += 1
if self.partition and self.partition[-1] == i:
self.rest += self.partition.pop()
while len(self.partition) >= 2 and self.partition[-1] + self.rest > self.partition[-1] * (self.partition[-1] - 1):
self.rest += self.partition.pop()
もう既に十分複雑化しているが、ここまでのものだけだと最後の分割を取り出した後、 さらに絞り出そうとして無限ループに陥ることがある。 その苦悩から救ってやるために shouldterminate も再定義する。 止まらなければならないケースでは True を返し、 続行できるケースでは False を返す。 だいたい先ほどの説明が解ってもらえていれば下のコードの内容は摑めると思う。
def shouldterminate(self):
if not self.partition:
return True
n = self.rest + sum(self.partition)
if self.partition[0] >= self.rest + 1:
return False
return self.partition[-1] + self.rest > self.partition[0] * (self.partition[0] - 1)
思ったよりも長くなってしまったが、ともかく、分割の満たすべき性質をコードに落とせば、 毎回同じように使い回すループは書かなくてもいいようにクラスができている、という点さえ押さえてもらえれば十分である。
0 件のコメント:
コメントを投稿