それでも TeX でビンソートしたい人のための何か

2012/12/01 〜 2012/12/25

TeX & LaTeX Advent Calendar

〜TeX で騒げ、TeX で笑え〜

こちらは（ｒｙ

*  *  *

例の「TeXsort」では満足しない人のために、「変換して TeX プログラミング」でビンソートを取り扱う。配列を含むプログラムの変換の例。

Lua で「ビンソート」してみた

bin_sort(ary) で整数値の要素をもつ配列 ary を昇順に整列する（上書きする）。((なお、Lua では配列の添字は 1 から始まる。ary の長さ（＝要素数＝最大添字）を #ary と記述する。))ここでの処理では、まず配列を一度スキャンして最小値と最大値を求めた上で、その範囲の添字をもつ係数の「配列」ct((ary 中の最小値を 10、最大値を 20 とすると、ct[10]〜ct[20] の範囲だけが非 nil の値をもつ、ということ。「長さ」の概念がないので厳密には配列でなく連想配列である。))を用意する、という手順をとっている。それ以外は通常のビンソートの手順（Wikipedia「バケットソート」を参照*1）と同じである。

なお、bin_sort() だけ TeX で実装しても LaTeX で実行を確認できるコードが書けないので、ここでは動作確認のデモとして demo_bin_sort(x,...) という関数を用意している。引数の整数列からなる配列について bin_sort() を実行しその結果を表示している。

-- 整数型: j, k, m, min, max
-- 配列型: ct  (ary は引数)

--(公開) bin_sort(配列ary)
-- 整数配列 ary を昇順に整列する. (結果で上書きする.)
function bin_sort (ary)
  -- 入力データの最小値, 最大値を求める
  min = ary[1]; max = min
  for k = 1, #ary do
    if min > ary[k] then min = ary[k] end
    if max < ary[k] then max = ary[k] end
  end
  -- 計数の配列を初期化
  ct = {}
  for m = min, max do
    ct[m] = 0
  end
  -- 計数を行う
  for k = 1, #ary do
    m = ary[k]; ct[m] = ct[m] + 1
  end
  -- 計数結果に基づき値を並べる
  k = 0
  for m = min, max do
    for j = 1, ct[m] do
      k = k + 1; ary[k] = m
    end
  end
end

---- 以下はデモ用コード

--(公開) demo_bin_sort(整数,...)
-- デモ用に以下の処理を行う.
-- * 引数(可変個数)の整数からなる配列を作成する.
-- * その内容を表示する.
-- * 配列を bin_sort() で整列する.
-- * 再び内容を表示する.
function demo_bin_sort(...)
  ary = { ... }
  print_array(ary)
  bin_sort(ary)
  print_array(ary)
end

--(公開) print_array(配列ary)
-- 配列 ary の内容を出力する.
function print_array(ary)
  for k = 1, #ary do
    io.write(""..ary[k].." ")
  end
  io.write("\n")
end

-- メイン
demo_bin_sort(3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 9)

実行結果。

3 1 4 1 5 9 2 6 3 5 8 9 
1 1 2 3 3 4 5 5 6 8 9 9 

さて、例によって、配列変数は「名前参照」の形に書き換えることになるが、その際に「配列変数の引数」というのが問題になる。*2「名前参照」で配列 ary を表現した場合、「ary 自体に相当するオブジェクト（モノ）」は存在しない。従って、配列自体は "ary" という名前（文字列）で指示することになる。

もう一つの問題は「配列の長さ」である。Lua では配列 ary の長さを #ary で得ることができるが、「名前参照」ではそのような機能は備わっていないし、また配列の長さを求める手段も存在しない。*3そこで、ここでは、「ary という名前の『配列』の長さは『ary/*』という名前の変数に入っている」という規則を採用することにする。もちろん ary の要素を書き換えたときに ary/* が自動更新されるわけではないので、必要な時に正しい値を入れておく必要がある。

書き換え後のコードは以下のようになった。

-- 整数型: j, k, l, m, min, max
-- 配列型: ct

--(公開) bin_sort(配列名)
function bin_sort (_1)
  min = _G[_1.."/1"]; max = min
  l = _G[_1.."/*"] -- 配列の長さ
  k = 0
  while k < l do
    k = k + 1
    m = _G[_1.."/"..k]
    if min > m then min = m end
    if max < m then max = m end
  end
  m = min; m = m - 1
  while m < max do
    m = m + 1
    _G["ct/"..m] = 0
  end
  k = 0
  while k < l do
    k = k + 1
    m = _G[_1.."/"..k]
   _G["ct/"..m] = _G["ct/"..m] + 1
  end
  k = 0
  m = min; m = m - 1
  while m < max do
    m = m + 1
    l = _G["ct/"..m]
    j = 0
    while j < l do
      j = j + 1
      k = k + 1; _G[_1.."/"..k] = m
    end
  end
end

---- 以下はデモ用コード

--(公開) demo_bin_sort(整数,...)
function demo_bin_sort(...)
  k = 0
  for _, m in pairs({...}) do -- 可変個数引数部分の for-each
    k = k + 1
    _G["ary/"..k] = m
  end
  _G["ary/*"] = k  -- 長さを設定する
  print_array("ary")
  bin_sort("ary")
  print_array("ary")
end

-- print_array(配列名)
function print_array(_1)
  l = _G[_1.."/*"]
  k = 0
  while k < l do
    k = k + 1
    io.write("".._G[_1.."/"..k].." ")
  end
  io.write("\n")
end

-- メイン
demo_bin_sort(3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 9)

demo_bin_sort() 冒頭の「引数列を配列 ary に読み込む」部分は、「えるたそ」（eltaso4.lua）と同じように @for マクロで実装する予定なので、それに合わせた処理になっている。前述のように、ここで「ary/*」という変数に配列の長さを設定する必要がある。

TeX で「ビンソート」してみた

パッケージ名は tcbinsort、名前空間は tcbs。公開命令は \binsort{<名前>} およびデモ用の \demobinsort{<整数>,...}（コンマ区切りで複数値指定）である。

% tcbinsort.sty
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{tcbinsort}

%% 変数定義
%(整数値)
\newcount\tcbs@j
\newcount\tcbs@k
\newcount\tcbs@l
\newcount\tcbs@m
\newcount\tcbs@min
\newcount\tcbs@max
%(配列型)
%\tcbs@ct/*

\def\tcbs@nameedef#1{%
  \expandafter\edef\csname#1\endcsname
}

%%(公開) \binsort{配列名}
\newcommand*{\binsort}[1]{%
  \tcbs@min=\@nameuse{tcbs@#1/1}\relax \tcbs@max=\tcbs@min
  \tcbs@l=\@nameuse{tcbs@#1/*}\relax
  \tcbs@k=0
  \@whilenum \tcbs@k<\tcbs@l \do{%
    \advance\tcbs@k 1
    \tcbs@m=\@nameuse{tcbs@#1/\the\tcbs@k}\relax
    \ifnum \tcbs@min>\tcbs@m \tcbs@min=\tcbs@m \fi
    \ifnum \tcbs@max<\tcbs@m \tcbs@max=\tcbs@m \fi
  }%
  \tcbs@m=\tcbs@min \advance\tcbs@m -1
  \@whilenum \tcbs@m<\tcbs@max \do{%
    \advance\tcbs@m 1
    \tcbs@nameedef{tcbs@ct/\the\tcbs@m}{0}%
  }%
  \tcbs@k=0
  \@whilenum \tcbs@k<\tcbs@l \do{%
    \advance\tcbs@k 1
    \tcbs@m=\@nameuse{tcbs@#1/\the\tcbs@k}\relax
    \tcbs@j=\@nameuse{tcbs@ct/\the\tcbs@m}\relax \advance\tcbs@j 1
    \tcbs@nameedef{tcbs@ct/\the\tcbs@m}{\the\tcbs@j}%
  }%
  \tcbs@k=0
  \tcbs@m=\tcbs@min \advance\tcbs@m -1
  \@whilenum \tcbs@m<\tcbs@max \do{%
    \advance\tcbs@m 1 \tcbs@j=0
    \tcbs@l=\@nameuse{tcbs@ct/\the\tcbs@m}\relax
    \@whilenum \tcbs@j<\tcbs@l \do{%
      \advance\tcbs@j 1 \advance\tcbs@k 1
      \tcbs@nameedef{tcbs@#1/\the\tcbs@k}{\the\tcbs@m}%
    }%
  }%
}%

%%%% 以下はデモ用コード

%%(公開) \demobinsort{値,...}
\newcommand*{\demobinsort}[1]{%
  \tcbs@k=0
  % \@for のループ「変数」はマクロ(=文字列変数)であることに注意
  \@for\tcbs@x:=#1\do{% \@for\tcbs@m:=... はダメ
    \advance\tcbs@k 1
    \tcbs@nameedef{tcbs@ary/\the\tcbs@k}{\tcbs@x}%
  }%
  \tcbs@nameedef{tcbs@ary/*}{\the\tcbs@k}%
  % ↑ここまで読込部
  \tcbs@print@array{ary}%
  \binsort{ary}%
  \tcbs@print@array{ary}%
}

%% \tcbs@print@array{配列名}
\def\tcbs@print@array#1{%
  \tcbs@l=\@nameuse{tcbs@#1/*}\relax
  \tcbs@k=0
  \@whilenum \tcbs@k<\tcbs@l \do{%
    \advance\tcbs@k 1
    \@nameuse{tcbs@#1/\the\tcbs@k}\space
  }%
  \par
}

\endinput

テスト用文書は以下の通り。

\documentclass[a4paper]{article}
\usepackage{tcbinsort}
\begin{document}
\demobinsort{3,1,4,1,5,9,2,6,5,3,5,8,9}
\end{document}