たかだか4文字の交換による撹乱順列の生成について  [in Japanese] Generating Derangements by Interchanging at Most 4 Elements  [in Japanese]

Search this Article

Author(s)

Abstract

集合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である.

Journal

  • The Transactions of the Institute of Electronics,Information and Communication Engineers.

    The Transactions of the Institute of Electronics,Information and Communication Engineers. 86(2), 69-74, 2003-02-01

    The Institute of Electronics, Information and Communication Engineers

References:  7

Cited by:  5

Codes

  • NII Article ID (NAID)
    110003171227
  • NII NACSIS-CAT ID (NCID)
    AA11341020
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09151915
  • NDL Article ID
    6452538
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-779
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top