文献

J-GLOBAL ID：201302253908001214   整理番号：13A0008088

撹乱順列の線形時間ランダム生成について

Linear time generation of random derangements

著者 (2件)： 三河賢治 (新潟大 情報基盤セ) ,  田中賢 (神奈川大 理)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 274(MSS2012 30-44)  ページ： 53-58  発行年： 2012年10月25日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本報告では,撹乱順列をランダムに生成するアルゴリズムを提案する。これまでに発表されたアルゴリズムは,順列をランダムに生成するアルゴリズムを改良し,ランダムに生成された順列のうち,撹乱順列となるものだけを出力するアルゴリズムであった。既存のアルゴリズムは厳密な線形時間生成ではなく,ならし線形時間で生成することを確率的に保証していた。提案アルゴリズムは,厳密な線形時間生成を実現する。(著者抄録)

シソーラス用語： *順列 ,  擾乱 ,  *アルゴリズム ,  ランダム処理 ,  計算量 ,  確率モデル ,  組合せ論 ,  *組合せ問題 ,  高速化
準シソーラス用語： ランダマイゼーション ,  *撹乱順列 ,  線形時間アルゴリズム

分類 (3件)： システム・制御理論一般  (IA02010H) ,  計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (4件)： 撹乱 ,  順列 ,  線形 ,  ランダム生成