Custom post type AND Category in permalink

http://www.tashmina.co.uk
I would ideally like:
http://www.domain.com/category/posttype/postname for each(custom)post, but I cannot find how to do this.
I am using the plugin Custom Post Type UI but this gives me permalinks which have
http://www.domain.com/posttype/postname
I need to also include the category in the permalink.
I have searched everywhere but cannot solve this. I did find a plugin but it didn’t work: I added custom permalnks for the custom post types but it did not understand /%catgegory%/

Can anyone help?