codeiq#468 https://codeiq.jp/ace/yuki_hiroshi/q468 の提出コードと出力。 漸化式に頼らず n 番目のナムドット行を計算するようにしています。

numdot.js

var numbase,
    numdot_len = 5;

/* Bell 数を計算します */
function bellNumber(n, l) {
  var i, cur_l = [], prev_l;
  if (l == undefined) {
    l = [[1]];
  }
  if (n <= 1) {
    return l.slice(-1)[0].slice(-1)[0];
  }
  prev_l = l.slice(-1)[0];
  cur_l.push(prev_l[prev_l.length - 1]);
  for (i = 0; i < prev_l.length; ++i) {
    cur_l.push(prev_l[i] + cur_l[i]);
  }
  l.push(cur_l);
  return bellNumber(n - 1, l);
};

/* n 個の配列 [0, 0, 0, ...] を生成します */
function intArray(n) {
  if (n <= 0) {
    return [];
  }
  return [0].concat(arguments.callee(n-1));
}

/* 数字から numdot へ変換するのに必要な表を作成します */
function makeNumbase(n) {
  var numbase = intArray(n).map(function(n, i, l) {
    return intArray(l.length - i);
  });
  return numbase.map(function(l, i, numbase) {
    if (i == 0) {
      return l.map(function(n, j, l){
        return numbase[i][j] = 1;
      });
    }
    return l.map(function(n, j, l) {
      return numbase[i][j] = (numbase[i-1][j] * (j+1)) + numbase[i-1][j+1];
    });
  });
}

/* 位置リストから numdot 文字列を生成します */
function numdotToStr(l) {
  var i, results = intArray(l.length).map(function(){ return ""; });

  l.map(function(v, i) { results[v] += (i+1); });

  return results.join('.').replace(/\.*$/, '');
}

/**
 * 指定した数の numdot を作成します
 * @n int    取得したいインデックス位置
 * @len int  使用される数字の数 ("13.2" なら 3 つ)
 **/
function indexOfNumdot(n, len) {
  var num = n, j = 0, result = [];
  numbase.slice(len ? -len : 0).map(function(l, i, numbase) {
    var d = parseInt(num / l[j]);
    d = (d > (j + 1)) ? (j + 1) : d;
    if (d) {
      result.push(d);
      num -= l[j] * d;
      j = Math.max(j, d);
      return;
    }
    result.push(0);
  });
  return numdotToStr(result);;
}

numbase = makeNumbase(numdot_len).reverse();

for(var i = 0; i < bellNumber(numdot_len); ++i) {
  console.log(indexOfNumdot(i, numdot_len));
}

numdotBase.md

コード概要

1. numdot の規則性

12345
1234.5
1235.4
123.45
123.4.5
1245.3
...

5 が常にドットの右へ移動しようとします。
右に移動した際に .. と連ドットを作った場合には一番左へ戻り、4(自分より一つ小さい値) を右へ移動させます。
他の値も連ドットを作った場合に同様に処理します。

---

2. 各数字が何番目のグループにいるかを保持させます

ここで各数字をドットを使わずに表現します。

           1  2  3  4  5
12345   = (0)(0)(0)(0)(0)
1234.5  = (0)(0)(0)(0)(1)
123.4.5 = (0)(0)(0)(1)(2)

のように n 番目のグループ、または自身の左にあるドットの数を示します。

これを表にすると次のようになります。

番号	1　2　3　4　5	numdot
0	(0)(0)(0)(0)(0)	12345
1	(0)(0)(0)(0)(1)	1234.5
2	(0)(0)(0)(1)(0)	1235.4
3	(0)(0)(0)(1)(1)	123.45
4	(0)(0)(0)(1)(2)	123.4.5
5	(0)(0)(1)(0)(0)	1245.3
6	(0)(0)(1)(0)(1)	124.35
7	(0)(0)(1)(0)(2)	124.3.5
8	(0)(0)(1)(1)(0)	125.34
9	(0)(0)(1)(1)(1)	12.345
10	(0)(0)(1)(1)(2)	12.34.5
11	(0)(0)(1)(2)(0)	125.3.4
12	(0)(0)(1)(2)(1)	12.35.4

任意の桁は自身より上位桁の最高値 +1 を超えない範囲で上昇している事が分かります。

これらの(0)について数学的に適切な名称があるのかも知れませんが、存じてないため便宜的に
(0)(0)(0)(0)(0)
の各桁を出題者の名前から 結城dig (digit:桁) と呼ぶことにします。

---

3. 結城dig の進数について

2 進数で各 bit が 1 2 4 8 16 32 であるように、
結城dig の各桁の値を特定することが出来れば、
任意の数字から numdot を生成する事ができるようになります。

まず各桁が純粋に 1 を示す時の値を調べます。

例えば
1: (0)(0)(0)(0)(1): 1234.5
の一桁目の 結城dig (1) は 1 を表しています。

また
2: (0)(0)(0)(1)(0): 1235.4
は二桁目の 結城dig (1) が 2 を表しています。

そして
5: (0)(0)(1)(0)(0): 1245.3
では三桁目の 結城dig (1) は 5 を表しています。

ここから次の numdot
(0)(0)(1)(0)(1): 124.35
は
(5 * 1) + (1 * 1) = 6
で 6 番目の numdot であると計算可能です。

ただし上記の numdot は例外的であり正しい計算方法は他にあり、
例えば
(0)(0)(1)(2)(0)
は 11 番目の numdot ですが、
(5 * 1) + (2 * 2) + (1 * 0) = 5 + 4 = 9
と計算しても間違った値が得られます。

これにより

• そもそも bit のようには計算できない
• 立式に失敗している

のどちらかが考えられます。

今回は条件立てをして上記の式を変形することで計算を完成することができます。
そしてその条件とは各 結城dig は上位桁の 結城dig の影響を受ける、ということです。

---

4. 結城dig の値

前章の計算を網羅すると 結城dig が以下のように値を取ると分かります。

上位の 結城dig の最高値 ＼ n 桁目の 結城dig	0	1	2	3	4
0	1	2	5	15	52
1	1	3	10	37
2	1	4	17
3	1	5
4	1

これも名前があると便利なので 結城digテーブル(表) としておきます。

この表の作成アルゴリズムについて触れると、
n 桁目、上位の 結城dig の最高値を m としたとき

F(n, m) = F(n-1, m) * (m+1) + F(n-1, m+1)

です。

例えば　n=2 桁目、結城dig の最高値 m=1 である 10 を出す計算は

F(2, 1) = F(2-1, 1) * (1+1) + F(2-1, 1+1)
        = 3 * 2 + 4
        = 6 + 4
        = 10

です。

「左の数」を「左下の数の行番号」でかけて「左下の数」を足すと出来上がりです。

---

5. numdot から番号を計算する

※ 以下長くなるため n を桁数、m を上位桁の 結城dig の最高値 とします

 4  3  2  1  0 桁
(0)(1)(0)(2)(1)
13.25.4

4 桁目の計算

n=4, m=0 より
4:0 = 52 を用います。

結城dig は 0 のため
52 * 0 = 0

3 桁目の計算

n=3, m=0 より
3:0 = 15 を用います。

結城dig は 1 のため
15 * 1 = 15

     上位桁の 結城dig の最高値は m=1 になります。

2 桁目の計算

n=2, m=1 より
2:1 = 10 を用います。

結城dig は 0 のため
10 * 0 = 0

1 桁目の計算

n=1, m=1 より
1:1 = 3 を用います。

結城dig は 2 のため
3 * 2 = 6

ここで上位桁の 結城dig の最高値が 2 になります。

0 桁目の計算

n=0, m=2 のため
0:2 = 1 を用います。

結城dig は 1 のため
1 * 1 = 1

全ての桁を合計します。
0 + 15 + 0 + 6 + 1 = 22

確認すると計算に用いた numdot は 0 を始点にした際の 22 番目(1を始点にすると23番目)の numdot と一致します。

---

6. 番号から numdot を計算する

下位桁は上位桁の影響を受けるので上位桁から計算を行います。

上位の 結城dig の最高値 ＼ n 桁目の 結城dig	0	1	2	3	4
0	1	2	5	15	52
1	1	3	10	37
2	1	4	17
3	1	5
4	1

先程の 22 を用いて検算を行います。

最初は全ての桁が未知です。

 4  3  2  1  0 桁
(_)(_)(_)(_)(_)

n=4, m=0 より
4:0 = 52 を用います。

22 / 52 = 0 ... 22

4 桁目は 0 になり、下位桁の計算に 22 が送られます。

 4  3  2  1  0 桁
(0)(_)(_)(_)(_)

n=3, m=0 より
3:0 = 15 を用います。

22 / 15 = 1 ... 7

3 桁目は 1 になり下位桁の計算に 7 が送られます。

上位桁の 結城dig は 1 になります。

 4  3  2  1  0 桁
(0)(1)(_)(_)(_)

n=2, m=1 より
2:1 = 10 を用います。

7 / 10 = 0 ... 7

2 桁目は 0 になり下位桁の計算に 7 が送られます。

 4  3  2  1  0 桁
(0)(1)(0)(_)(_)

n=1, m=1 より
1:1 = 3 を用います。

7 / 3 = 2 ... 1

1 桁目は 2 になり下位桁の計算に 1 が送られます。

上位桁の 結城dig は 2 になります。

 4  3  2  1  0 桁
(0)(1)(0)(2)(_)

n=0, m=2 より
0:2 = 1 を用います。

1 / 1 = 1

0 桁目は 1 になり計算終了です。

 4  3  2  1  0 桁
(0)(1)(0)(2)(1)

このように数字から numdot を生成することができました。

今回の例では出ませんでしたが、
計算時は 結城dig が上位桁を越さないようにする必要があります。

output.txt

12345
1234.5
1235.4
123.45
123.4.5
1245.3
124.35
124.3.5
125.34
12.345
12.34.5
125.3.4
12.35.4
12.3.45
12.3.4.5
1345.2
134.25
134.2.5
135.24
13.245
13.24.5
135.2.4
13.25.4
13.2.45
13.2.4.5
145.23
14.235
14.23.5
15.234
1.2345
1.234.5
15.23.4
1.235.4
1.23.45
1.23.4.5
145.2.3
14.25.3
14.2.35
14.2.3.5
15.24.3
1.245.3
1.24.35
1.24.3.5
15.2.34
1.25.34
1.2.345
1.2.34.5
15.2.3.4
1.25.3.4
1.2.35.4
1.2.3.45
1.2.3.4.5