おおよそ並べ：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞おおよそ並べ

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

おおよそ並べ

デニス・シャシャ

　マッスルムービング社は彫刻の移動を請け負った。彫刻を重さの順に一列に並べ直すのが仕事だ。ただ，理想の位置でなくとも，それに十分近い位置でおおよその順で並べればいいという。彫刻の列が理想的な列からどのくらいずれているのかを「k違い」で示す。これは，それぞれの彫刻が，重さの順に並べたときの理想位置からたかだかk（k以下）だけ離れていることを示す。
　例えば，重さが１トン刻みに１～９トンまである９つの彫刻が下のように並んでいたとする（以下，彫刻はその重さの数字で，位置は漢数字で表す）。
　

彫刻	４	６	８	１	２	３	５	７	９
位置	一	二	三	四	五	六	七	八	九

　
９トンの彫刻は九番目の正しい位置にあるが，７トンの彫刻は八番目にあり，理想の位置から１ずれている。最も離れているのは三番目にある８トンの彫刻で，５だけ離れているから，この列は「５違い」だ。彫刻をいくつか移動させて，１違いの列にするとしよう。例えば，一番目の彫刻と四番目の彫刻を交換する。これを（一，四）と表記する。次に二番目と六番目の彫刻の位置を交換する。つまり（二，六）だ。
　

彫刻	１	３	８	４	２	６	５	７	９
位置	一	二	三	四	五	六	七	八	九

　
最後に（三，五）と（五，七）をすれば，
　

彫刻	１	３	２	４	５	６	８	７	９
位置	一	二	三	四	五	六	七	八	九

　
となり，１違いの列を得る。この例では，後ろ２つの彫刻の初期配置が理想的な位置に近かったのが幸いだった。
　
問１：下の初期配置では，５回の交換で１違いの列を得られる手順があるが，もっと短い手順は存在するか。
　

彫刻	９	８	７	１	４	３	５	６	２
位置	一	二	三	四	五	六	七	八	九

　
問２：次の初期配置で１違い列を得るには何回の交換が必要か（ヒント：この問題の方が問１よりも難しい）。
　

彫刻	３	５	６	７	８	１	９	２	４
位置	一	二	三	四	五	六	七	八	九

　
問３：マッスル社は，与えられた９個の彫刻の列を１違い列にするのに必要な交換回数の最大値を知りたい。１違い列にするのに最も多くの交換が必要な配置を求めよ（ヒント：最小値の最大化問題が問われていることに注意。その配置に対する最小交換回数がわかったとして，それが最も大きい配置を問われている）。
　
問４：n個の異なる数の列が与えられたとして，それを（n－１）違い列にするのに必要な交換回数はあきらかに０だ。各nに対し，d違い列にするのに最も多くの交換回数が必要な配置を見つけることができるか。また，その場合に必要な交換回数はいくらか（ヒント：答えは驚くほど単純で美しい）。
　
問５：N個の異なる要素からなる１違い列は何通りか（ヒント：この答えも非常に単純で美しい）。

GARY ZAMCHICK

	山崎秀記（やまさき・ひでき）

	一橋大学商学部教授。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Close Enough （SCIENTIFIC AMERICANのウェブサイト http://www.sciam.com/より）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved