Paper Abstract and Keywords |
Presentation |
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 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
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. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
permutation / adjacent transposition / Universal sequence / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 119, no. 191, COMP2019-10, pp. 1-5, Sept. 2019. |
Paper # |
COMP2019-10 |
Date of Issue |
2019-08-26 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
COMP2019-10 |
|