Non crossing set partitions

I have a Mathematica package for generating Catalan objects on GitHub, so I have some recursive algorithm which generates what you want. Moreover, it has a nice graphical representation of these, and some operations on these, such as rotation.

Just download the package, and do

Needs["CatalanObjects`"]
Last /@ NonCrossingPartitions[4]

to get

{{{1, 2, 3, 4}}, {{3}, {1, 2, 4}}, {{2}, {1, 3, 4}}, {{1, 4}, {2, 
   3}}, {{2}, {3}, {1, 4}}, {{1}, {2, 3, 4}}, {{1}, {3}, {2, 4}}, {{1,
    2}, {3, 4}}, {{1}, {2}, {3, 4}}, {{4}, {1, 2, 3}}, {{2}, {4}, {1, 
   3}}, {{1}, {4}, {2, 3}}, {{3}, {4}, {1, 2}}, {{1}, {2}, {3}, {4}}}

If you do not want everything in the package, it should be easy to extract the method.

Needs["Combinatorica`"]

ClearAll[nonCrossingSetPartitions]
nonCrossingSetPartitions = 
    DeleteCases[{___, {___, a_, ___, c_, ___}, ___, {___, b_, ___, d_, ___}, ___} /;
       a < b < c < d] @* SetPartitions;

nonCrossingSetPartitions @ 4 // Column

nonCrossingSetPartitions @ 5 // Length

42