講演抄録/キーワード |
講演名 |
2019-09-02 10:50
Shortest Universal Sequences of Adjacent Transpositions Takehiro Ito(Tohoku Univ.)・Jun Kawahara・Shin-ichi Minato(Kyoto Univ.)・Yota Otachi(Kumamoto Univ.)・Toshiki Saitoh(Kyutech)・Akira Suzuki(Tohoku Univ.)・Ryuhei Uehara(JAIST)・Takeaki Uno(NII)・○Katsuhisa Yamanaka(Iwate Univ.)・Ryo Yoshinaka(Tohoku Univ.) COMP2019-10 |
抄録 |
(和) |
$S = {s_1,s_2, ... , s_m}$を$[n] = {1,2,ldots ,n}$の隣接互換の列とする.
$S$中の互換を,$s_1$から$s_m$の順に合成して得られる置換を$Comp(S) = s_m circ s_{m-1} circ cdots circ s_1$と書く. $S$中の全ての区間からなる集合を$Inter(S)$と書く. ここで, $Perm(S) = {Comp(S) | S' in Inter(S)}$と定義する. このとき, $S$が$Perm(S) = Sym([n])$を満たすならば,$S$は$Sym([n])$に対してユニバーサルであるという.ここで, Sym([n])は,$[n]$の全ての置換からなる集合である. 本稿では, Sym([n])に対するユニバーサル列を求める問題を扱い,最短長のユニバーサル列の長さについて調査する. |
(英) |
Let $S = {s_1,s_2, ... , s_m}$ be a sequence of adjacent transpositions of $[n]={1,2,ldots ,n}$. We denote by $Comp(S) = s_m circ s_{m-1} circ cdots circ s_1$ the composition of transpositions in $S$ from $s_1$ to $s_m$. Let us denote by $Inter(S)$ the set of all the intervals of $S$. We define $Perm(S) = {Comp(S) | S' in Inter(S)}$. Then, we say that $se$ is textit{universal} for Sym([n]) if $Perm(S) = Sym([n])$ holds, where Sym([n]) is the set of the permutations of $[n]$. We consider the problem of finding an universal sequence for Sym([n]) and investigate the length of a shortest universal sequence. |
キーワード |
(和) |
置換 / 隣接互換 / ユニバーサル列 / / / / / |
(英) |
permutation / adjacent transposition / Universal sequence / / / / / |
文献情報 |
信学技報, vol. 119, no. 191, COMP2019-10, pp. 1-5, 2019年9月. |
資料番号 |
COMP2019-10 |
発行日 |
2019-08-26 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2019-10 |