Permalink problems with custom post type and custom taxonomy

There was a problem with archive page and pagination in the original answer. Therefore, instead of changing the "rewrite" => ['slug' => 'our-training/%training-category%'] in register_post_type()
as I suggested earlier, add the following rewrite rules and change the links created for CPT.

The rules will handle such addresses:

• display single training post with pagination support

/our-training/training-category-1/training-name/
/our-training/training-category-1/training-name/2/

• display training posts assigned to training-category-1 (uncomment first rewrite rule)
  note: this is query for taxonomy term, not cpt, so the first available template from the list will be used: taxonomy-training_category.php > taxonomy.php > archive.php

/our-training/training-category-1/
/our-training/training-category-1/page/2/

Default rules will handle:

• display all training posts (archive)

/our-training/

• display all posts (any type, “event”, “employee”, etc.) assigned to training-category-1

/training-category/training-category-1/

This code worked for me.

add_action( 'init', 'se391612_cpt_permalink', 20 );
add_filter( 'post_type_link', 'se391612_term_in_cpt_link', 20, 4 );

function se391612_cpt_permalink()
{
    //
    // CPT posts from custom taxonomy term (term archive)
    //add_rewrite_rule(
    //    'our-training/([^/]+)(?:/page/?([0-9]+))?/?$', 
    //    'index.php?post_type=training&training_category=$matches[1]&paged=$matches[2]',
    //    'top'
    //);    
    //
    // single post with pagination 
    add_rewrite_rule(
        'our-training/([^/]+)/([^/]+)(?:/([0-9]+))?/?$', 
        'index.php?post_type=training&training=$matches[2]&page=$matches[3]',
        'top'
    );
}

function se391612_term_in_cpt_link( $post_link, $post, $leavename, $sample )
{
    if ( ! $post instanceof \WP_Post || 'training' != $post->post_type)
        return $post_link;
    $new_link = $post_link;
    $all_terms = wp_get_post_terms( $post->ID, 'training_category', [
        'hide_empty' => '0',
        'fields' => 'slugs',
        'orderby' => 'term_id',
    ] );
    if ( !is_array($all_terms) || 0 == count($all_terms) )
        return $post_link;

    $term = array_shift($all_terms) . "https://wordpress.stackexchange.com/";
    $new_link = str_replace('our-training/', 'our-training/'.$term, $new_link);

    return $new_link;
}

Important note:
If you uncomment the first add_rewrite_rule() to support /our-training/training-category-1 permalink format,
an address collision will occur. For WP there is no difference between these addresses,
how it interprets them depends on the order of rewrite rules.

/our-training/training-category-1   // all "training" post from category "training-category-1"
/our-training/some-training-name    // single "training" post

However, if you would like both address types to work
and you know that there will be only several categories, you can add
these categories in the rules (manually or automatically).

---

Reference:
register_post_type()
wp_get_post_terms()
post_type_link filter