Skip to content

Instantly share code, notes, and snippets.

@chaoxu
Created July 6, 2011 00:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chaoxu/1066286 to your computer and use it in GitHub Desktop.
Save chaoxu/1066286 to your computer and use it in GitHub Desktop.
Word Problem for B_3
--Word Problem for B_3
--Input a word, 1 = generator \sigma_1, 2 = generator \sigma 2, -1 and -2 are their inverse respectively.
--Return true if it's trivial, else return false
isTrivialBraid3 list =
(remainword == []) && (pdelta+delta == 0)
where (remainword, pdelta) = positiveDelta' word [] 0
(word,delta) = negativeDelta' list [] 0
positiveDelta' before after delta
| (suffix == [1,2,1] || suffix == [2,1,2]) = positiveDelta' before (drop 3 after) (delta + 1)
| before == [] = (after, delta)
| otherwise = positiveDelta' (init before) ((move (last before) delta):after) delta
where suffix = take 3 after
negativeDelta' before after delta
| before == [] = (after, delta)
| x == -1 = negativeDelta' (xs++[1,2]) after (delta-1)
| x == -2 = negativeDelta' (xs++[2,1]) after (delta-1)
| otherwise = negativeDelta' xs ((move x delta):after) delta
where x = last before
xs = init before
move sigma delta
| ((mod delta 2) == 0) = sigma
| otherwise = 3-sigma
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment