I suspect you might have a better chance of getting useful replies if you were to manually create a small example list of permuted integers for a small N, a set small enough that it is easy understand, but just large enough that it will show each of the kinds of cases that might arise. Then manually show what the result should be after you perform your operation on these sets and explain why.

It might not be precisely clear to some readers exactly what "gather them in subsublists where all elements differ only by one unit" means and without that understanding it might be difficult to offer the code idea you are looking for.

Thank you. That helps.

You are doing lots of small integer operations. My first thought is to compare your code with a compiled version of your code.

I quit the kernel, evaluate x=0 to get the kernel loaded and then I evaluate your function.

In[1]:= x = 0

Out[1]= 0

In[2]:= AbsoluteTiming[
 k = 0; ll = Range[12]; n = 7;
 For[i = 1, i <= 10^6, i++, 
  k += Length[Split[Sort[RandomSample[ll, n], Less], #1 - #2 == -1 &]]
 ];
 k]

Out[2]= {19.4494, 3500839}

Now I quit the kernel, evaluate x=0 and then I evaluate the compiled version.

In[1]:= x = 0

Out[1]= 0

In[2]:= cfun = Compile[{},
   k = 0; ll = Range[12]; n = 7;
   Do[
    k += Length[Split[Sort[RandomSample[ll, n]], #1 - #2 == -1 &]]
    , {10^6}];
   k];
AbsoluteTiming[cfun[]]

Out[3]= {15.3916, 3500458}

So that is 19.4 seconds versus 15.4 seconds. That isn't enough of an increase.

Perhaps someone else can think of another way to increase this even more.

Good catch. Thank you for pointing out my mistake.

I didn't take time to check that because I (incorrectly) assumed all those steps looked simple enough that they would compile without complaint.

Perhaps you can experiment with small changes to this until you isolate what is causing the compile to hook back to the Mathematica evaluator and then see if you can think of a simple way to rewrite that.

If I had to bet then I would expect it is the user defined function being given to Split that isn't compiling. Replacing that with some very simple iterative code might fix the problem.

That then might give the 3-10x increase in speed.

I would also watch for the size of the total being accumulated in k because it looks like it might overflow with larger exponents.

Just to elaborate a little:

t = Table[Sort[RandomSample[ll, 7], Less], {10^5}]

How can I write a function (I assume with Map) so that it will return the number of non-consecutive neighbor discontinuities in each sublist, say 12356710 has two discontinuities? The above written Split is slow. I think there should be other faster way without drastically reorganizing the list.

This is great! Faster 20 times! I need one more order of magnitude and that's it.

Split is a problem here. It's up in a few comments.