このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

プログラミング課題:第一象限の格子点をたどる

実務上の必要性から生じた話なんですが、「問題としてちょっと面白いかもな」と思ったので紹介します。特別なアイディアやトリッキーな方法は不要なのでクイズという感じじゃないですね。普通に「プログラミングの練習問題」でしょう。算術計算だけで出来るので、プログラミング言語や実行環境は問いません。

n次元単体

0次元単体とは1個の点、1次元単体とは線分、2次元単体とは内部を含む三角形、3次元単体とは内部を含む四面体です。もっと次元が高いn次元単体(simplex)は類推してください。

単体は三角形の一般化なので、n次元単体をΔnと書くことが多いですが、σnとかsnとかを使うこともあります。ここでは、単体の特別な(そして標準的な)実現を、σn、snで表すことにします。

n次元のユークリッド数空間をRnとします*1。σnRn+1の部分集合、snRnの部分集合として次のように定義します。

  • σn = {(x1, ..., xn, xn+1)∈Rn+1 | x1 ≧ 0, ..., xn ≧ 0, xn+1 ≧ 0, x1 + ... + xn + xn+1 = 1}
  • sn = {(x1, ..., xn)∈Rn | x1 ≧ 0, ..., xn ≧ 0, x1 + ... + xn ≦ 1}

σ0, σ1, σ2, s1, s2, s3 を絵に描くと次のようです。

格子点

σnとsnに非負数値のパラメータkを導入して次のように定義します。

  • σn(k) = {(x1, ..., xn, xn+1)∈Rn+1 | x1 ≧ 0, ..., xn ≧ 0, xn+1 ≧ 0, x1 + ... + xn + xn+1 = k}
  • sn(k) = {(x1, ..., xn)∈Rn | x1 ≧ 0, ..., xn ≧ 0, x1 + ... + xn ≦ k}

ここで、連続な空間Rnの代わりに、座標が整数である空間Znを考えます。座標が整数である点は格子点と呼びます。以下、σn、snの定義も格子点に限定します(でも、同じ記号を使い続けます)。パラメータkも非負整数に限定します。

四面体=三角錐をスライスする状況を考えると、次のことがわかります。

  • sn+1(k) = σn(0) + σn(1) + ... + σn(k)

ここでプラス記号「+]は集合の合併なのですが、集合の直和になっているので「∪」より「+」のほうが感じが出ます。

第一象限の格子点の列挙

(n+1)次元の格子点空間Zn+1で、すべての座標が非負であるような格子点の全体は“第一象限”を形成します。第一象限は、次のような無限直和で書けます。

  • σn(0) + σn(1) + σn(2) + ...

これは、sn+1(k)のkを無限に飛ばした形をしているので、記号的には「第一象限 = sn+1(∞)」と書いてもいいでしょう。

さて問題は、N = {0, 1, 2, 3, ...} として、N→sn+1(∞) という双射(全単射写像を作ってください、というものです。n = 0 のとき、N→s1(∞) は自明です。

この双射写像は、sn+1(∞) = σn(0) + σn(1) + σn(2) + ... というスライス構造を尊重するようにしてください。つまり、最初にσn(0)を列挙し、次にσn(1)を列挙し、それからσn(2)を列挙し、という具合です。

σn(k)に含まれる格子点の個数をN(n, k)として、{0, 1, ..., N(n, k)}→σn(k) という双射を先に考えるといいかもしれません。最終的には、すべてのnに対する fn:N→sn+1(∞) が欲しいのですが、fn達をひとつの2変数関数f(n, i)と考えると、f:N×N→Σn=0..∞[sn+1(∞)] となります。

大きなシグマは集合の無限総和のつもりですが、Σn=0..∞[sn+1(∞)]とは、非負整数を成分とする長さ任意のリスト達の集合のことです。

*1:ユークリッドとは言っても、計量は使いません。