جابه‌جایی چرخشی

در ریاضیات ترکیبیاتی، جابه‌جایی چرخشی یا جابه‌جایی دَوَرانی یا شیفت دوری عملیاتی است که درایه‌های یک چندتایی را با حرکت دادن درایه انتهایی به موقعیت آغازین آن، مجدداً آرایش می‌دهد، در حالی که تمام درایه‌های دیگر به مکان بعدی خود نقل مکان می‌کنند، یا با عملی معکوس با آنچه توصیف شد، در جهت مخالف جابه‌جایی آرایه‌ها صورت می‌پذیرد. جابه‌جایی دورانی نوع خاصی از جایگشت دوری است که به نوبه خود نوع خاصی از جایگشت است. به‌طور صوری، جابه‌جایی دورانی را می‌توان جایگشتی چون $\sigma$ از n عنصر در نظر گرفت که در یک چندتایی قرار دارند چنان‌که برای تمام $i=1,\cdots ,n$ به پیمانه n داریم:

ماتریس‌هایی از ۸ عنصر که به چپ و راس به صورت دورانی جابه‌جا شده‌اند.

$\sigma (i)\equiv (i+1)$

یا:

$\sigma (i)\equiv (i-1)$

برای نمونه، با اعمال جابه‌جایی دورانی به‌طور مکرر روی چندتایی چهارتایی $(a,b,c,d)$ به صورت پشت سر هم به نتایج زیر می‌رسیم:

• (d, a, b, c),
• (c, d, a, b),
• (b, c, d, a),
• (a, b, c, d)

که تاپل آخر، همان تاپل اولیه ما می‌باشد.

مثال

اگر دنباله بیتی $00010111$ تحت جابه‌جایی دورانی تک‌بیتی قرار بگیرد … (تصاویر زیر را ببینید):

به راست نتیجه می‌دهد: ۱۰۰۰۱۰۱۱. شیفت دوری به راست.

به چپ نتیجه می‌دهد: ۰۰۱۰۱۱۱۰ جابه‌جایی دورانی به چپ.

اگر دنباله بیتی $10010110$ تحت عملیات زیر قرار می‌گرفت:

جابه‌جایی چرخشی راست با ۱ موقعیت:	۰۱۰۰۱۰۱۱
جابه‌جایی چرخشی راست با ۲ موقعیت:	۱۰۱۰۰۱۰۱
جابه‌جایی چرخشی راست با ۳ موقعیت:	۱۱۰۱۰۰۱۰
جابه‌جایی چرخشی راست با ۴ موقعیت:	۰۱۱۰۱۰۰۱
جابه‌جایی چرخشی راست با ۵ موقعیت:	۱۰۱۱۰۱۰۰
جابه‌جایی چرخشی راست با ۶ موقعیت:	۰۱۰۱۱۰۱۰
جابه‌جایی چرخشی راست با ۷ موقعیت:	۰۰۱۰۱۱۰۱
جابه‌جایی چرخشی راست با ۸ موقعیت:	۱۰۰۱۰۱۱۰

جابه‌جایی چرخشی چپ با ۱ موقعیت:	۰۰۱۰۱۱۰۱
جابه‌جایی چرخشی چپ با ۲ موقعیت:	۰۱۰۱۱۰۱۰
جابه‌جایی چرخشی چپ با ۳ موقعیت:	۱۰۱۱۰۱۰۰
جابه‌جایی چرخشی چپ با ۴ موقعیت:	۰۱۱۰۱۰۰۱
جابه‌جایی چرخشی چپ با ۵ موقعیت:	۱۱۰۱۰۰۱۰
جابه‌جایی چرخشی چپ با ۶ موقعیت:	۱۰۱۰۰۱۰۱
جابه‌جایی چرخشی چپ با ۷ موقعیت:	۰۱۰۰۱۰۱۱
جابه‌جایی چرخشی چپ با ۸ موقعیت:	۱۰۰۱۰۱۱۰

جستارهای وابسته

• حلقه (جایگشت‌ها)
• عملیات بیتی
• جابه‌جاکننده بشکه‌ای

منابع

جابه‌جایی دورانی