Created
July 6, 2011 00:31
-
-
Save chaoxu/1066286 to your computer and use it in GitHub Desktop.
Word Problem for B_3
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--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