いかにして表計算の列名をつくるか・補遺

先日Rubyで書いたものをRuby以外のメジャーどころの言語でも実装してみます。

桁上がりで１文字戻す

Ruby

再掲。

def column_names(n)
  result = ''
  begin
    result = (n % 26 + 65).chr + result
    n = n / 26 - 1
  end while n >= 0
  result
end

C++

#include <string>

std::string column_names(int n)
{
    std::string result;
    do
    {
        result = char(n % 26 + 'A') + result;
        n = n / 26 - 1;
    } while(n >= 0);
    return result;
}

Haskell

import Data.Char(chr)

reversed_column_names :: Integer -> String
reversed_column_names (-1) = []
reversed_column_names n = (chr $ fromInteger $ n `mod` 26 + 65):(column_names $ n `div` 26 - 1)

column_names :: Integer -> String
column_names = reverse.reversed_column_names

追加する文字をリストの後ろに追加していけば最後に反転する必要がなくなるのですが、文字を追加するたびに文字列を構築するよりも、一旦構築した文字列を反転する方が低コストのはずなので、このようにしています。
あと、Prologへの布石ですね。

Prolog

reversed_column_names(-1, []).
reversed_column_names(N, [R|XS]) :- R is mod(N, 26) + 65, N1 is div(N, 26) - 1, reversed_column_names(N1, XS).
column_names(N, S) :- reversed_column_names(N, S1), reverse(S1, S).

実行方法を書いておかないと（主に未来の自分が）検証ができないので、実行法をメモしておきます。
処理系には SWI-Prolog を利用しています。

$ swipl -s column_names.prolog -g 'column_names(200, S), format("~s~n", [S]), halt'
GS

-s オプションで上記のプログラムを保存したファイルのファイル名を指定します。

-g オプションでゴールを指定します。
column_names(200, S)を実行しただけでは結果が出力されないので、format("~s~n", [S])で結果を表示しています。format/2の書式はこちらを参照してください。
haltを指定することで、実行後にコマンドを終了させています。終了させないとプログラムの実行後に SWI-Prolog のプロンプトが表示されます。

やっぱりみんな大好き、直積

Ruby

再掲。

AtoZ = [*?A..?Z]
column_names = AtoZ + AtoZ.product(AtoZ).map(&:join) + AtoZ.product(AtoZ).product(AtoZ).map(&:join)

この例では3桁までの文字列しか生成していませんが、無限に続くばあいの扱いに長けた言語があるので、それで実装してみます。

Haskell

A〜Z の並びを A とし、直積を×で、文字列の並びの連結を＋で表すと、列名の配列 column_names は次のようになります。

column_names = A + A × A + A × A × A + …

これを次のように変形します。

column_names = A + (A + A × A + … ) × A

すると括弧の中が column_names になるので、つまり次のように書くことができます。

column_names = A + column_names × A

これを実装すると。こんな感じになりました。

import Data.List(group)

column_names_ :: [String] -> [String]
column_names_ ss = ss ++ (map concat $ sequence [column_names_ ss, ss])

column_names :: [String]
column_names = column_names_ $ group ['A'..'Z']

A〜Z の並びを作るために group を使っているところとか、map concat とかがいまいちあか抜けない感じですが、一応目指すやり方で実装することができました。

（2014/08/05 修正: sequence [column_names_ ss, ss]とすべきところがsequence [column_names, ss]となっていました）