تابع $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$ را پیدا کرد.