floyd cycle detection algorithm


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

Source Code

-- Floyd cycle finding algorithm
-- See: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

-- Detects cycle in a given sequence
-- f : a function which returns the next element (i.e f(x0) = x1, f(x1) = x2, ...)
-- x0 : the initial element
-- returns : the cycle (loop) position, or tail
-- returns : the cycle (loop) length
return function (f, x0)
  local tortoise = f(x0)
  local hare = f(f(x0))

  while tortoise ~= hare do
  if not tortoise or not hare then return nil end    
    tortoise = f(tortoise)
    hare = f(f(hare))
  end

  local mu = 0
  tortoise = x0
  repeat
    tortoise = f(tortoise)
    hare = f(hare)
    mu = mu + 1
  until tortoise == hare
  
  local lambda = 1
  hare = f(tortoise)
  while tortoise ~= hare do
    hare = f(hare)  
    lambda = lambda + 1
  end
  
  return lambda, mu
end
-- Tests for floyd.lua
local floyd = require 'floyd'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Floyd cycle detection test', function()
  local t = {}
  for i = 1,7 do t[i] = {} end
  for i = 1,6 do t[i].next = t[i+1] end
  t[7].next = t[2]
  
  local function f(n) return n and n.next end
  local len, tail = floyd(f, t[1])
  assert(len == 6 and tail == 1)
  
  t[7].next = t[5]
  len, tail = floyd(f, t[1])
  assert(len == 3 and tail == 4)
  
  t[7].next = nil  
  assert(floyd(f, t[1]) == nil)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))