Generating Brainf*** NOPs

CJam, 118 116 bytes

This got slightly out of hand... especially the second half seems like it should be very golfable.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Test it here.

This handles N = 100 pretty much instantly. I don't have time to write the full breakdown of the code now, so here is the algorithm:

• Generate a random balanced string of < and > with random (even) length between 0 and N inclusive.
• Riffle the tape head positions into this array. E.g. "<>><" becomes [0 '< -1 '> 0 '> 1 '< 0].
• Get a list of all positions reached in the process.
• For each such position initialise an empty string. Also determine how many pairs of characters are left to reach a string of length N.
• For each remaining pair append +- to the string of a random position.
• Shuffle all of those strings.
• For each position determine how often that position occurs in the riffled array, and split the corresponding string into that many (random-length) chunks.
• In the riffled array, replace the occurrences of the position with its random chunks.

Done. This is based on the observation that:

• Any NOP must have an equal amount of < and > to return the tape head to the original position.
• The code will be a NOP as long as each tape cell is incremented as often as decremented.

By distributing random but balanced amounts of +s and -s between all the places where the tape head is on a given cell, we ensure that we find every possible NOP.

CJam, 62 59 bytes

Thanks to nhahtdh for saving 3 bytes.

Because there is no requirement for any particular distribution as long as each no-op appears with finite probability, we can simplify this a lot by simply generating string containing a balanced number of -+ and <>, respectively, testing if it's a NOP and sorting it if it isn't.

Of course, for longer inputs, this will almost always result in sorted output, but you can test the code with some input like 8 to see that it can in principle produce any NOP of the given length.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

Try it online.

Mathematica, 350 bytes

Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

Way too long? Yes. Do I even care? Not until someone else posts a valid answer.