| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-11-02 11:00 撹乱順列の線形時間ランダム生成について ○三河賢治（新潟大）・田中 賢（神奈川大）  CAS2012-59 MSS2012-39 |
|
| 抄録 | （和） | 本報告では，撹乱順列をランダムに生成するアルゴリズムを提案する．これまでに発表されたアルゴリズムは，順列をランダムに生成するアルゴリズムを改良し，ランダムに生成された順列のうち，撹乱順列となるものだけを出力するアルゴリズムであった．既存のアルゴリズムは厳密な線形時間生成ではなく，ならし線形時間で生成することを確率的に保証していた．提案アルゴリズムは，厳密な線形時間生成を実現する． |
| （英） | We present a linear time algorithm for generating random derangements. Several algorithms published in recent papers enhanced the well-known Fisher-Yates shuffle for random permutations to suit this problem with using the rejection method so that the algorithms generated random permutations sequentially and picked up only derangements by omitting the other permutations. The algorithms were ensured to run in an amortized linear time in probabilistic analysis. Our algorithm achieves an exact linear time generation of random derangements. | |
| キーワード | （和） | 組合せ問題 / アルゴリズム / ランダム生成 / 線形時間 / 撹乱順列 / / / |
| （英） | combinatorial problem / algorithm / random generation / linear time / derangement / / / | |
| 文献情報 | 信学技報, vol. 112, no. 273, CAS2012-59, pp. 53-58, 2012年11月. | |
| 資料番号 | CAS2012-59 | |
| 発行日 | 2012-10-25 (CAS, MSS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2012-59 MSS2012-39 |
|
| 研究会情報 | |
| 研究会 | MSS CAS |
| 開催期間 | 2012-11-01 - 2012-11-02 |
| 開催地（和） | 岩手大学 |
| 開催地（英） | Iwate University |
| テーマ（和） | グラフ、ペトリネット、ニューラルネット及び一般 |
| テーマ（英） | Graph, Petri Net, Neural network, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | CAS |
| 会議コード | 2012-11-MSS-CAS |
| 本文の言語 | 日本語 |
| タイトル（和） | 撹乱順列の線形時間ランダム生成について |
| サブタイトル（和） | |
| タイトル（英） | Linear time generation of random derangements |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 組合せ問題 / combinatorial problem |
| キーワード(2)（和/英） | アルゴリズム / algorithm |
| キーワード(3)（和/英） | ランダム生成 / random generation |
| キーワード(4)（和/英） | 線形時間 / linear time |
| キーワード(5)（和/英） | 撹乱順列 / derangement |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 三河 賢治 / Kenji Mikawa / ミカワ ケンジ |
| 第1著者 所属（和/英） | 新潟大学 (略称： 新潟大) Niigata University (略称： Niigata Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 田中 賢 / Ken Tanaka / |
| 第2著者 所属（和/英） | 神奈川大学 (略称： 神奈川大) Kanagawa University (略称： Kanagawa Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-11-02 11:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CAS |
| 資料番号 | CAS2012-59, MSS2012-39 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.273(CAS), no.274(MSS) |
| ページ範囲 | pp.53-58 |
| ページ数 | 6 |
| 発行日 | 2012-10-25 (CAS, MSS) |
[研究会発表申込システムのトップページに戻る]