Woocommerce redirection product_name -> product_cat/product_name

You could try the template_redirect action. Check if current request is a single product.
@see https://codex.wordpress.org/Plugin_API/Action_Reference/template_redirect

add_action( 'template_redirect', function() {

    //= bail early
    if( !is_404() ) return;

    //= get product name from url
    $product_name = get_query_var( 'pagename' );

    //= bail
    if( empty( $product_name ) ) return;

    //= lookup product by name
    $product = get_page_by_path( $product_name, OBJECT, 'product' );

    //= bail
    if( is_null( $product ) ) return;

    //= redirect
    wp_redirect( get_the_permalink( $product->ID ) );
    exit;

} );

Note #1 in addition you might want to check if query_var “product_cat” is empty. Otherwise you might end up with an infinite loop.

Note #2 try to add some logic ( add it if it doesn’t exist, otherwise skip logic ) to pass the redirect to the Redirection plugin. Idea above will run on every request. If it’s just a redirect sitting in the Redirection plugin, it will be faster.

Hope this sets you on the right track.
Sorry I don’t have the exact solution.