Location : Home > Languages > Perl > Package
Title : Algorithm::Numerical::Shuffle
 		Toolbox Logo

名称

　Algorithm::Numerical::Shuffle - リストをシャッフルする

概要

use Algorithm::Numerical::Shuffle qw /shuffle/;

@shuffled = shuffle (1, 2, 3, 4, 5, 6, 7);

$in_situ = [qw /one two three four five six/];
shuffle $in_situ;

説明

　リストを入力とし、それをシャッフルした結果を返す。配列参照を渡された場合にはそのままで（in situ）処理する。サブルーティンはリストが渡されればリストで返し、リスト参照が渡されればスカラーで返す。

複雑さ

　アルゴリズムの実行時間はリストのサイズに線形である。そのままで shffule の場合メモリのオーバヘッドは一定であるが、そうでない場合は別のメモリを利用する。

文献

　使用したアルゴリズムは Knuth [3] で議論されたものである。これは最初、 Fisher 及び Yates [2] によって公開され、後に Durstenfeld [1] も公開したものである。

注意

　Salfi [4] では重要な注意点を指摘している。乱数生成法が線形合同法（linear congruential method）のように直前の出力値のみに依存しているのであれば、結果はシャッフルアルゴリズム・入力値・乱数生成の種によって決定されることになる。このことから、所与のリストとアルゴリズムに対してはシャッフルの結果は種にのみ依存する。最近の多くのコンピュータは32ビットの乱数を持っており、32ビットの種となる。すると可能なアルゴリズムに対して可能な種の数は最大 2^32 となる。
　しかし n 個の要素のリストには n! 個の順列が可能である。これは、 13! > 2^32 であることから、13個の要素からなるリストからの順列は作れないことを意味する。

参照

  1. R. Durstenfeld: CACM, 7, 1964. pp 420.
  2. R. A. Fisher and F. Yates: Statistical Tables. London, 1938. Example 12.
  3. D. E. Knuth: The Art of Computer Programming, Volume 2, Third edition. Section 3.4.2, Algorithm P, pp 145. Reading: Addison-Wesley, 1997. ISBN: 0-201-89684-2.
  4. R. Salfi: COMPSTAT 1974. Vienna: 1974, pp 28 - 35.

履歴

$Date: 2000/03/08 05:57:40 $

$Log: Shuffle.pm,v $
 Revision 1.4  2000/03/08 05:57:40  abigail
 バグを修正
 ライセンスの言い回しを変更(MIT/X style)

Revision 1.3  1999/03/01 20:54:06  abigail
 パッケージ名称を Algorithm::* に変更
 ライセンスを変更

Revision 1.2  1998/09/09 20:48:12  abigail
 - 空リストに対しても shuffle() が稼動するように機能追加
 - ライセンスを Artistic のみに変更

Revision 1.1  1998/04/23 17:58:07  abigail
 初期バージョン

著者

　本パッケージは Abigail によって書かれた。

著作権

　Copyright 1998, 1999, 2000 by Abigail.

ライセンス

　本プログラムは Abigail に著作権がある。

　以下に定める条件に従い、本ソフトウェアおよび関連文書のファイル（以下「ソフトウェア」と記す）の複製を取得するすべての人に対し、ソフトウェアを無制限に扱うことを無償で許可する。これには、ソフトウェアの複製を使用・複写・変更・結合・掲載・頒布・サブライセンス及び／または販売する権利、およびソフトウェアを提供する相手に同じことを許可する権利も無制限に含まれる。
　上記の著作権表示および本許諾表示を、ソフトウェアのすべての複製または重要な部分に記載するものとする。
　ソフトウェアは「現状のまま」で、明示であるか暗黙であるかを問わず、何らの保証もなく提供される。ここでいう保証とは、商品性・特定の目的への適合性及び権利非侵害についての保証も含むが、それに限定されない。作者または著作権者は、契約行為・不法行為またはそれ以外であろうと、ソフトウェアに起因または関連し、あるいはソフトウェアの使用またはその他の扱いによって生じる一切の請求、損害、その他の義務について何らの責任も負わない。

Toolbox Logo
 Updated : 2006/07/12