با چه برنامهای و چگونه میتوانم جایگشت های زوجی که با یک جایگشت دادهشده جابجا شوند را محاسبه کنم؟

Question

لطفا برنامه‌ای معرفی کنید که با آن بتوانم تمام جایگشت‌های زوجی که با جایگشت زیر جابجا شوند را محاسبه کنم. $$(1\;2)\,(3\;4)\,\cdots\,(2n-1\;2n)$$ فکر کنم نرم‌افزار GAP باید بتواند این کار را انجام دهد ولی نمی‌دانم چگونه.

Comments

@Faribagrouptheory
- منظورتان از الگوریتم گپ چه هست؟ احتمالا منظورتان نرم‌افزار GAP است نه الگوریتم!

---

سلام بله نرم افزار گپ. البته نرم افزارش برام فرق نمیکنه و فقط به دنبال جواب هستم

Answer 1

پیش از پرداختن به بخش نرم‌افزاری چند تعریف را از جبر دربارهٔ گروه‌ها که به احتمال زیاد باید در دورهٔ کارشناسی آموخته‌باشید را به یاد می‌آوریم. فرض کنید $G$ یک گروه و $g$ یک عضو از آن باشد. آنگاه می‌گوئیم یک عضو $h$ از $G$ با $g$ جابجا می‌شود هر گاه داشته‌باشیم $gh=hg$ که از گذاشتن نماد عمل گروه صرف‌نظر کرده‌ایم با این تصور که متوجه هستید که زمانی که می‌نویسیم $gh$ منظورمان $g\cdot h$ است که «$\cdot$» عملِ گروه $G$ است. اگر نرم‌افزار یا کد برنامه‌نویسی‌تان مفهوم‌های گروه و عنصر را (دست‌کم برای گروه‌های جایگشتی که مدنظر پرسش‌تان است) تعریف‌شده داشته‌باشد آنگاه ساده‌ترین کدی که می‌توانید بنویسید این است که حلقهٔ for داشته‌باشد و برای تک‌تک عضوهای $h\in G$ دو عبارتِ $gh$ و $hg$ را محاسبه و سپس با یک شرط مقایسه‌ایِ «اگر $gh=hg$» عضوهای مناسب را به عنوان خروجی برایتان فهرست کند.

مفهوم دیگری که می‌توانید به یاد آورید مفهومِ «جابجاگر» است. برای دو عضو $g$ و $h$، جابجاگر این دو عضو با نماد $[g,h]$ نمایش داده‌می‌شد و به این شکل تعریف می‌شد. $$[g,h]=g^{-1}h^{-1}gh$$ توجه کنید که در حالت کلی ترتیب مهم است و الزاما $[g,h]$ با $[h,g]$ برابر نیست. به هر حال یک تمرین ساده که در درس جبر۱ داشتید این بود که «جابجاگر دو عضو برابر همانیِ گروه است اگر و تنها اگر این دو عضو با هم جابجا شوند». پس کد دیگری که می‌توانید بنویسید یک حلقهٔ for دارد که برای هر $h\in G$ جابجاگر $[g,h]$ را محاسبه می‌کند و اگر حاصل عضو همانی گروه شد آن را در بین عضوهای خروجی به نمایش می‌گذارد.

و اما آخرین تعریفی که می‌خواهیم در اینجا (پیش از نرم‌افزار) مرور کنیم. یک تمرین سادهٔ دیگر که به یک تعریف می‌انجامد این است که می‌توانید به سادگی نشان دهید که مجموعهٔ همهٔ عضوهای گروه که با یک عضو جابجا شوند تشکیل یک زیرگروه می‌دهد. یعنی مجموعهٔ $\lbrace h\in G\mid gh=hg\rbrace$ یک زیرگروه از $G$ است. این زیرگروه را «مرکزی‌سازِ عضو $g$ در گروه $G$» صدا می‌کنند.

نرم‌افزارهای پیش‌رفتهٔ ریاضی که نظریهٔ گروه‌ها را نیز جزو هدف‌هایشان قرار داده‌اند معمولا گروه‌های جایگشتی، دورها، و زیرگروه‌های پایه مانند همین مرکزی‌ساز را از پیش برایشان دستور تعریف کرده‌اند و کد برایش نوشته‌اند. نرم‌افزارهای زیادی کار با گروه‌ها را دارند. یکی از این نرم‌افزارها Mathematica است که در زیر چند دستورش که برای پرسش شما به کار می‌آیند را معرفی کرده‌ایم.

برای تعریف گروه جایگشت‌های روی مجموعهٔ $n$تایی یعنی $S_n$ از دستور SymmetricGroup[n] استفاده کنید که $n$ یک عدد طبیعی است. برای عضوهای این گروه باید از نمایش‌شان به شکل حاصلضرب دورهای مجزا از هم استفاده کنید (یعنی همان تجزیه‌شان به دورها). برای نمونه برای عضوی که تجزیه‌اش به دورهای مجزا به شکل $(1\;5\;7)(3\;4)$ است از دستور Cycles[{{1,5,7},{3,4}}] استفاده کنید. توجه کنید که جلوی Cycles همیشه یک کروشه باز و بسته کنید، سپس یک اَبرو (آکولاد) باز و بسته کنید، تا اینجا همیشه باشد انجام شود. سپس در داخل این ابرو هر دور را بای یک ابرو و عددهای داخل دور بنویسید و با گذاشتن ویرگول بین ابروهای دورها آنها را از هم جدا کنید. توجه کنید که نباید عددی در چند دور ظاهر شود و گر نه تجریه‌تان به دورهای مجزا نبوده‌است. برای یافتنِ مرکزی‌ساز از دستور‌ GroupCentralizer[G,g] استفاده کنید. توجه کنید که خروجیِ Mathematica برای این دستور، یک مولد برای این زیرگروه است (به یاد آورید که مولد مجموعه‌ای از عنصرها بود که گروه را تولید می‌کردند). برای دیدن همهٔ عضوهای گروه از دستورِ GroupElements[G] استفاده کنید. در زیر پرسش شما را برای $G=S_4$ و $g=(1\;2)(3\;4)$ با Mathematica انجام داده‌ایم.

G = SymmetricGroup[4]
g = Cycles[{{1, 2}, {3, 4}}]
H = GroupCentralizer[G, g]
GroupElements[H]

برای اینکه خروجی‌هایش را در خود محیط Mathematica نیز ببینید، شکل زیر را نگاه کنید.

که اگر بخواهید به شکل استاندارد ریاضی آنها را از نو بنویسید، به شکل زیر می‌شوند: $$\begin{array}{l} (1)\\ (3\;4)\\ (1\;2)\\ (1\;2)(3\;4)\\ (1\;3)(2\;4)\\ (1\;3\;2\;4)\\ (1\;4\;2\;3)\\ (1\;4)(2\;3) \end{array}$$ یعنی از ۲۴ عضوِ $S_4$ هشت عضو با $g$ جابجا می‌شوند که در بالا آمده‌اند و ۱۶ عضو دیگر که نیامده‌اند با $g$ جابجا نمی‌شوند.

و اما زوج و فرد بودن جایگشت‌ها. اگر تعریف آن را یادتان رفته‌است می‌توانید به یک مرجع جبر۱ کارشناسی یا کتاب پایه که مفاهیم پایهٔ نظریهٔ گروه را معرفی می‌کند مانند کتاب جبر نوشتهٔ محمدی حسن‌آبادی منتشر شده بوسیلهٔ انتشارات دانشگاه اصفهان یا به کتاب Abstract Algebra نوشتهٔ David Dummit و Richard Foote نگاه کنید. به هر حال یک گزارهٔ مفید داشتیم که می‌گفت «یک دور با درازای $n$ زوج است اگر و تنها اگر منهای یک به توان درازایش مثبت یک شود و در غیر اینصورت فرد است» و همینطور داشتیم که «یک جایگشت $g$ زوج است اگر و تنها اگر حاصلضرب منهای یک به توان درازای دورهای حاضر در تجزیه‌اش به ضرب دورهای مجزا از هم برابر با مثبت یک شود و در غیر اینصورت فرد». پیشنهاد خود توسعه‌دهندگان Mathematica برای نوشتن یک کد که یک جایگشت را بگیرد و زوج و فرد بودنش را به شکل $1$ و $-1$ بدهد، کدِ زیر است.

permutationSignature[perm_?PermutationCyclesQ] := 
 Apply[Times, (-1)^(Length /@ First[perm] - 1)]

اگر این کد را در صفحه‌تان اجرا کنید، از آن زمان به بعد با نوشتنِ permutationSignature[g] زوج و فردیِ $g$ را خواهید گرفت. پس کافیست که حلقهٔ For بر روی عضوهای $H$ای که در بالا یافتیم بنویسیم که دارای یک شرط است که اگر این عضوها زوج بودند آنها را در لیست جدیدی بریزد و در آخر این لیست که تنها عضوهای زوج را دارد را به ما تحویل بدهد. اما توجه کنید که در حلقهٔ Forمان باید عنصرِ $i$اُم را به شرط بدهیم برای گرفتن عضوِ $i$اُمِ یک گروه می‌توانید به دستوری که تمام اعضا را می‌داد یک سفارش (تنظیم) اضافه کنید، اگر داخل ابرو چند عدد طبیعی بنویسید که بین ۱ و تعداد عضوهای گروه است، آنگاه خروجی لیستی تنها شامل عضوهای با اندیس‌های تعیین شده توسط شما خواهد بود و نه تمام عضوها. پس ما یک اندیس و آن هم $i$ را داخل ابرو گذاشته و به دستور می‌افزائیم یعنی. GroupElements[H,{i}]. ولی خروجی یک ابرو زیادی دارد! ما تنها خودِ عضوِ $i$اُم را می‌خواستیم ولی به ما مجموعهٔ تک‌عضویِ شامل این عضو را داده‌است. برای اینکه خود این عضو را بیگیریم و از شر ابروی اضافهٔ دورش رها شویم کافیست بگوئیم عضوِ یکمِ این لیست را به ما بده. برای گرفتنِ عضوِ $i$اُمِ یک لیست در Mathematica باید نام لیست و سپس $i$ در داخل یک کروشهٔ دوبله را بنویسیم. پس اگر اسم لیست‌مان L باشد آنگاه عضو یکم آن را به این شکل فراخوانی می‌کنیم L[[1]]. همیشه مراقب باشید که یک کروشه معنای متفاوتی در Mathematica دارد. یک کروشه برای گرفتن ورودی‌های یک دستور است و دوکروشه برای گرفتن اندیس درایه در یک لیست یا آرایه. آخرین چیزی که نیاز داریم تا بتوانیم کدمان را نهایی کنیم این است که چگونه تعداد عنصرهای یک گروه را خودکار بگیریم. شاید در مثال دیگری نتوانستیم عنصرها را مانند اینجا یکی یکی بشماریم و بفهیمیم ۸ عضو داریم، فرض کنید گروهی که در محاسبهٔ دیگری پیدا کردید بیشتر از هزار عنصر داشت، در این حالت تک‌تک شمردن پیشنهاد خوبی نیست. دستورِ آماده‌ای در Mathematica هست و آن GroupOrder[G] است. راه دیگر این است که لیست تمام عضوها را بگیرید و بگوئید تعداد عضوهایش را بشمارد. برای شمارش تعداد عضوهای یک لیست با نام L از دستورِ Length[L] استفاده کنید. به هر حال. کدِ نهایی که در آن Heven نام لیستی است که جایگشت‌های زوجِ داخلِ $H$ را قرار می‌دهیم به شکل زیر است. در ابتدا آن را لیستی خالی تعریف می‌کنیم و سپس به کمک یک For و If اعضای مناسب را به آن می‌افزائیم. برای افزودن عنصر a به لیست L از دستورِ AppendTo[L,a] استفاده می‌کنیم.

Heven = {};
For[i = 1, i <= GroupOrder[H], i++,
  If[permutationSignature[GroupElements[H, {i}][[1]]] == 1,
    AppendTo[Heven, GroupElements[H, {i}][[1]]]
    ];
  ];

حاصل و همینطور نکته‌های دیگری که اشاره شد را در محیط خود Mathematica در شکل زیر می‌بینیم.

مجموعهٔ مورد نظر یعنی جایگشت‌هایِ عضوِ $S_n$ که هم با $(1\;2)(3\;4)$ جابجا می‌شوند و زوج هم هستند به شرح زیر هستند. $$\begin{array}{l} (1)\\ (1\;2)(3\;4)\\ (1\;3)(2\;4)\\ (1\;4)(2\;3) \end{array}$$