تابع ‎$F$‎ تابعی یک‌به‌یک و پوشا است. بنابراین یک جایگشت از اعداد ‎1‎ تا ‎$n$‎ است. فرض کنید که اعداد ‎$a_0$‎، ‎$a_1$‎، ‎$\cdots$‎ ، ‎$a_k-1$ شماره رئوس یکی از دورهای گراف جایگشت تابع ‎$F$‎ باشد. فرض کنید که ‎$G$‎ به شکلی تعریف شده باشد که ‎$a_0$‎ را به ‎$b_0$‎ نگاشت کند و ‎$b_0$‎ در جایگشت ‎$F$‎ در دوری به طول ‎$p$‎ قرار داشته باشد.

این دور را با اعداد ‎$b_0$‎, ‎$b_1$‎, ‎$\cdots$‎ , ‎$b_p-1$‎ نشان می‌دهیم. (ممکن است این دور همان دور ‎$a_0$‎و ‎$a_1$‎و ‎$\cdots$‎ و ‎$a_p-1$‎ باشد‎(.‎

تابع ‎$F$‎ تابعی یک‌به‌یک و پوشا است. بنابراین یک جایگشت از اعداد ‎1‎ تا ‎$n$‎ است. فرض کنید که اعداد ‎$a_0$‎و ‎$a_1$‎و ‎$\cdots$‎ و ‎$a_{k-1}$‎ شماره رئوس یکی از دورهای گراف جایگشت تابع ‎$F$‎ باشد. فرض کنید که ‎$G$‎ به شکلی تعریف شده باشد که ‎$a_0$‎ را به ‎$b_0$‎ نگاشت کند و ‎$b_0$‎ در جایگشت ‎$F$‎ در دوری به طول ‎$p$‎ قرار داشته باشد. این دور را با اعداد ‎$b_0$‎, ‎$b_1$‎و ‎$\cdots$‎ و ‎$b_{p-1}$‎ نشان می دهیم. (ممکن است این دور همان دور ‎$a_0$‎و ‎$a_1$‎و ‎$\cdots$‎ و ‎$a_{p-1}$‎ باشد‎(.‎ $$‎ f(g(a_0 ) )= g(f(a_0 ) ) \Rightarrow f(b_0 )= g(a_1 ) \Rightarrow b_1=g(a_1)$$

بنابراین تابع ‎$G$‎ باید ‎$a_1$‎ را هم به ‎$b_1$‎ نگاشت کند و همین طور می توان نشان داد که به ازای هر ‎$1 \leq i \leq k$‎، رابطه‌ی زیر برقرار است‎:‎ ‎ $$g(a_i)= b_{(i \mod p)}$$ ‎ بنابراین برای اینکه تابع ‎$G$‎، هر رأس از گراف جایگشت را فقط به یک رأس دیگر نگاشت می کند (خاصیت تابع)، باید ‎$k$‎ بر ‎$p$‎ بخشپذیر باشد. پس درواقع تابع ‎$G$‎ باید به این شکل باشد که رئوس هر دور از گراف جایگشت را که مثلا اندازه‌اش ‎$k$‎ می باشد به دوری دیگر از جایگشت که مثلا اندازه‌اش ‎$p$‎ است نگاشت می کند به طوری که حتما ‎$K$‎ بر ‎$p$‎ بخشپذیر است. به سادگی می توان نشان داد که این شرط کافی هم هست تا تابع ‎$G$‎ با تابع ‎$F$‎ همگام باشد‎.‎

مثلا ‎$G$‎ می تواند هر دور از گراف جایگشت ‎$F$‎ را به خودش ببرد به این شکل که تابع ‎$G$‎ تابع همانی باشد. اما ما کوچک‌ترین تابع ‎$G$‎ همگام با ‎$F$‎ را می‌خواهیم. برای مینیمم کردن تابع ‎$G$‎ باید هر دور گراف جایگشت ‎$F$‎ را مستقلا مینیمم کنیم. برای این کار کافیست به ازای هر دور در این گراف مثل ‎$C$‎ که اندازه‌اش ‎$k$‎ می‌باشد، دوری مثل ‎$C’$‎ با اندازه‌ی ‎$p$‎ پیدا کنیم که اولا ‎$k$‎ بر ‎$p$‎ بخشپذیر باشد و دوما شماره کوچک‌ترین رأس در دور ‎$C’$‎ مینیمم باشد. سپس رأس با مینیمم شماره در دور ‎$C$‎ مثل ‎$u$‎ را به رأس با مینیمم شماره در رأس ‎$C’$‎ مثل ‎$v$‎ نگاشت می‌کنیم و بقیه‌ی رئوس را به ترتیب دوری به هم نگاشت می‌کنیم.

برای یافتن دور ‎$C’$‎ و رأس ‎$u$‎ می‌توان از الگوریتمی شبیه غربال اراتستن استفاده کرد. به این طریق که به ازای هر دور در گراف که طولش ‎$k$‎ و مینیمم رأس در آن ‎$u$‎ است، در یک آرایه‌ی ‎$n$‎ تایی به اسم ‎best‎ تمام مقادیر ‎$k$‎ و ‎$2 \times k$‎ و‎$3 \times k$‎ و ‎$\cdots$‎ را با مقدار ‎$u$‎ بروزرسانی می‌کنیم. سپس برای اینکه برای دور ‎$C$‎ با طول ‎$p$‎ دور بهینه‌ی ‎$C’$‎ را بیابیم، با استفاده از مقدار ‎best[p]‎، رأس مناسب ‎$u$‎ را پیدا می کنیم‎.

پیچیدگی

یافتن دورهای گراف جایگشت ‎$F$‎ با ‎$O(n)$‎ بوسیله‌ی الگورتمی مثل ‎DFS‎ امکان‌پذیر است. سپس با روشی شبیه غربال اراتستن آرایه best‎ را مقداردهی می‌کنیم. نکته‌ی قابل توجه در این مرحله این است که برای اینکه پیچیدگی زمانی این قسمت از ‎$O(n \log n)$‎ شود، باید در ابتدا به ازای هر ‎$1 \leq i \leq n$‎، دور بهینه به طول ‎$i$‎ را پیدا کنیم و سپس از روی best[i]‎ مقادیر best[2i] و best[3i] و ‎$\cdots$‎ را بروزرسانی کنیم. بعد از بروزرسانی آرایه‌ی ‎best‎، به ازای هر دور ‎$F$‎ با ‎$O(d)$‎ که ‎$d$‎ تعداد رئوس این دور باشد، می توان مقادیر ‎$G$‎ برای رئوس این دور را به‌دست آورد که در مجموع از ‎$O(n)$‎ زمان می‌برد‎.‎ بنابراین در کل از ‎$O(n \log n)$‎ می‌توان کوچک‌ترین تابع همگام با ‎$F$‎ را پیدا کرد‎.‎