Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Tortoise and hare algorithm

Tags:

algorithm

I was reading Tortoise and hare algorithm from wikipedia. I am wondering whether the python pseudocode is wrong. It seems to fail for the array: [1, 2, 2, 3, 4, 5, 6, 7, 8, 9, ....] as at the very beginning, the two values meet and the algorithm continues to find the start of the cycle which is doomed to failure.
I understand that there is condition of i ≥ μ, should this constraint be added to the code for finding the start of the cycle?
If this constraint is added, should the algorithm terminate and return no cycle found when failed or continue for another iteration? Since what if the input is [1, 2, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5, ....] ?
How does this algorithm guarantee that at the first meeting point, both pointers are inside some cycles?

like image 720
Ra1nWarden Avatar asked Feb 11 '23 13:02

Ra1nWarden


1 Answers

The tortoise and hare algorithm runs two pointers, one at offset i and the other at offset 2i, both one-based, so initially 1 and 2, and is meant to detect cycles in linked-list-style data structures.

And, just to be clear, it compares the pointers rather than data values they point to, I'm unsure whether you understand that so, on the off-chance you didn't, I just thought I'd mention it.

The initial start point is to have the tortoise on the first element and the hare on the second (assuming they exist of course - if they don't, no loop is possible), so it's incorrect to state that they're equal at the start. The pointer value can only ever become equal if the hare cycles and therefore catches the tortoise from behind.

like image 172
paxdiablo Avatar answered Feb 19 '23 17:02

paxdiablo