Rewrite permalinks for custom posttype and custom taxonomy

How to rewrite permalinks for a custom posttype and custom taxonomy?

I have a custom taxonomy: region, and a custom posttype: business.

Now, how to rewrite the permalink, so that

• for a category, the fixed “category” part is replaced with the custom taxonomy term:

  /%region%/%category%/

• for a business: /%region%/%category%/%business%/

I’m stuck with this. However, I did manage to rewrite the permalink for a region to /%region%/:

add_action( 'init', 'region_init' );
function region_init() {
  // set labels
    $labels = array(
    'name' => _x( 'Regions', 'taxonomy general name' ),
    'singular_name' => _x( 'Region', 'taxonomy singular name' ),
    'search_items' =>  __( 'Search Regions' ),
    'popular_items' =>  __( 'Popular Regions' ),
    'all_items' => __( 'All Regions' ),
    'parent_item' => __( 'Parent Region' ),
    'parent_item_colon' => __( 'Parent Region:' ),
    'edit_item' => __( 'Edit Region' ), 
    'update_item' => __( 'Update Region' ),
    'add_new_item' => __( 'Add New Region' ),
    'new_item_name' => __( 'New Region Name' )
  );
  // create a new taxonomy
  register_taxonomy(
    'region',
    'business',
    array(
      'labels' => $labels,
      'label' => __('Region'),
      'sort' => true,
      'args' => array('orderby' => 'term_order'),
      'show_in_nav_menus' => true,
      'query_var' => true,
      'rewrite' => array( 'slug' => '', 'with_front' => false )
    )
  );
}

add_action('init', 'my_rewrite');
function my_rewrite() {
    global $wp_rewrite;
    $wp_rewrite->add_permastruct('typename', 'typename/%year%/%postname%/', true, 1);
    add_rewrite_rule('typename/([0-9]{4})/(.+)/?$', 'index.php?typename=$matches[2]', 'top');
    $wp_rewrite->flush_rules(); // !!!
}

The Custom Post Permalinks (WordPress Plugin) from John P. Bloch did the trick for me. Great /flexible plugin!