たかだか4文字の交換による撹乱順列の生成について(<小特集>LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
集合S={1,2,...,n}に対して,π(i)≠iであるような置換π:S→Sは全換置換と呼ばれ,文字列π(1)π(2)...π(n)は撹乱順列と呼ばれる.本論文では,すべての撹乱順列を一つずつ含むようなリストの生成について考える.文字列上の文字を交換して順々に文字列を生成する逐次生成では,交換される文字数が少ないほど効率よくリストを生成できる.撹乱順列のリストをP(S),交換される文字数の最大値をdeg(P(S))とすると,今日までにdeg(P(S))=O(1)となるような撹乱順列のリストは知られていない.本論文では,撹乱順列は互いに素なサイクルに分解できることに注目して,deg(P(S))=2となるような撹乱順列のリストは存在しないことを示す.また論文後半では,|S|≧4についてdeg(P(S))=rとなるリストを生成するアルゴリズムを与える.このアルゴリズムによると,交換される文字数の平均はおよそ2.980である.
- 社団法人電子情報通信学会の論文
- 2003-02-01
著者
関連論文
- L-028 パケットフィルタリング最適化問題における多項式時間アルゴリズム(ネットワーク・セキュリティ,一般論文)
- ディジタル濃淡画像の三角平面パッチによるSVG形式への変換(コンピュータグラフィックス)
- Log-Polar変換による静脈画像の位置ずれ補正の提案(映像メディア処理,感性情報工学及び一般)
- Log-Polar変換による静脈画像の位置ずれ補正の提案
- ビット列で表現された完全二分木の判定アルゴリズム(計算理論とアルゴリズムの新展開)
- 再帰的に二等分割された直角二等辺三角形上の頂点数を求めるアルゴリズム(画像処理)
- 直角二等辺三角形の二等分割とその頂点数について (計算機科学基礎理論の新展開)
- 自然数の組成のO(1)時間生成について(アルゴリズム理論)
- 自然数の組成のO(1)時間生成について (計算機科学基礎理論の新展開)
- たかだか4文字の交換による撹乱順列の生成について(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- フィボナッチ列のO(1)時間生成について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 反復型アルゴリズムによるフィボナッチ列の生成について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 部分リストの反転によるk-順列の生成について(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 高々2回の交換によるカッコ列の高速生成法 (アルゴリズムと計算の理論)