I have a list of N elements which I need to sort (1, 2, 3, 4, ... ,N).
I can lock any subset of elements and shuffle the free elements.
Each shuffle permutes the free elements uniformly at random. Each permutation is equally likely.

I need to calculate the expected number (X) of shuffle operations when following the best lock-strategy.

Example:
N = 2
1,2
X = 0

N = 2
2,1
X = 2

N = 4
2,1,4,3
X = 4

N = 3
2,3,1
X = 3 = (1/6*1+1/2*3)+(1/6*1/3*2+1/2*1/3*4)+ ...

What about?
N = 4
3,1,2,4
X = 4.118 = (1/24*1+8/24*4+3/24*5+5/24*3)+7/24*(1/24*2+8/24*5+3/24*6+5/24*4)+...

Is there some smooth/elegant way to do these calculations?

N = 4
3,1,2,4
X = 4.59 = (1/24*1+8/24*5+3/24*5+5/24*3)+7/24*(1/24*2+8/24*6+3/24*6+5/24*4)+...

Maybe more mistakes ...

Is the best lock strategy known? Or is that what you're looking for?

They assume you know perfect strategy:

I thought this would be optimal:
Look for auto-locks (correct initial positions). Then look for 2-place switchers and make shuffles, then look for 3-place switchers and so on.
If this is correct, I need to calculate X (as elegant as possible).

2 place-switch:
Expected shuffles = 1/2*1 + 1/2*1/2*2 + 1/2*1/2*1/2*3 + ... = 2

Example:
N=5
2, 1, 4, 3, 5

I shuffle 2 - 1 and lock S, S, 4, 3, 5. Then I shuffle 4 - 3 and lock 1, 2, S, S, 5.
X = 2 + 2 = 4

Example:
N = 5
2, 3, 1, 5, 4

I shuffle 5 - 4 and lock 2, 3, 1, S, S. Then I shuffle 2 - 3 - 1 and lock S, S, S, 4, 5.
X = 2 + 3 = 5

Those are fairly easy but it could get pretty complex:
2, 3, 4, 1 or 2, 4, 5, 3, 1 or ...

So my question is actually is there some elegant way to calculate this for 4-place switchers or higher?

Am I correct in my approach to sort elements as fast as possible:

Start by perma-lock the 1-switchers (1XXXX or X2XXX), then look for 2-switchers (X32XX or XXX54) and perform switches, and so on until max N-switchers (53124).

To calculate the expected amount of shuffles (E) I add those several child-E's (21453 = 2-switcher and 3-switcher).
If I don't have the correct E for those childs I go down and for every permutation I calculate it the same way as for the parent E.

Is this the correct and fastest approach?

bump ... sry but I'm too eager to see a more elegant way to solve this.

You are right that you just have to add the values of the cycles (what you call children). The hard part, I think, is counting how many of each partition of cycles there are.

Here's what I would do for n=4, for example. The partitions are

4
3 1
2 2
2 1 1
1 1 1 1

Now we have to count how many there are of each partition

4: There are 3! of these, since we choose where 1 goes, then choose where the image of one goes, until we have no choices. So, 6.
3 1: There are 4 ways to choose the singleton and 2! ways to organize the 3-cycle, so, 8
2 2: C(4,2) = 6 ways to pick the 2 cycle (and the other is determined), but this double counts since you could've picked the other cycle first, so you get 3.
2 1 1: C(4,2) = 6 (since the other two are locked)
1 1 1 1: definitely only 1 way to do this.

So if we call X_n the expected value for X, then
X_4 = (6/24) (1+X_4) + (8/24) (X_3 + X_1) + (3/24) (X_2 + X_2) + (6/24) (X_2 + X_1 + X_1) + (1/24) (X_1 + X_1+X_1+X_1)

then you can solve for X_4.

It's kind of a mess but if I have some giant partition like N = 60 and

7 7 7 6 6 4 4 4 4 4 2 2 2 1

Then the fraction of permutations with cycles of these lengths are
1/(7! 7! 7! 6! 6! 4! 4! 4! 4! 4! 2! 2! 2! 1!) /(3! 2! 5! 3! 1!)

where the last guys are the numbers of identical sizes you have. Then you'd multiply this by X_7 + X_7 + X_7 + X_6 + ... , do this for all partitions and then solve for X_60.

It's a mess but it's not too hard to automate all this if you don't mind decimal rounding error. Although once you get to 60 I bet all these fractions may be so small that the error messes you up.

There probably is a faster way...

Thanks, I have to automate this for N<=1000 (so X_1000 max) which isn't too hard I guess.

Like in your example N=60 it could be that X_7 is the max:
Solution = X_7 + X_7 + X_7 + X_6 + ...

(no need to calculate X_8 or higher)

I've made mistakes in prev. posts itt concerning X_4 but now I have this:

(X_3, X_2, X_1 are already known beacause I build it up from X_1 to X_n)

X_4 = 3.9999... = (1/24*1+8/24*4+3/24*5+6/24*3) + 6/24*(1/24*2+8/24*5+3/24*6+6/24*4) + ...

X_5 and so on ...

But X_4 = 4 is the same as X_2+ X_2 = 4 ??
Am I missing something here?

Oh, I forgot a bunch of ones in my equation, it's wrong, sorry.

I think this may be a matter of definition too. I'm defining X_n = average amount of time to clear an n-cycle (an example of an n-cycle is if you were to have the list 2 3 4 ... n-1 n 1).
Clearly X_1 is 0. X_2 is 2 because if your list is (2 1), half the time it takes one shuffle, and the other half you are back where you started, so
X_2 = 1/2*(1) + 1/2(1 +x_2)
so X_2 = 2.
For X_3, 1/6 of the time you hit it in 1 shuffle, 3/6 of the time you get one locked and are down to a 2-cycle, and 2/6 of the time you are still in a 3-cycle (2 3 1 or 3 1 2). So
X_3 = 1/6(1) + 3/6(1 + X_2) + 2/6(1+X_3), so 2/3 X_3 = 2 and X_3 = 3.

The correct equation for X_4 should be

X_4 = (6/24) (1+X_4) + (8/24) (1 + X_3 + X_1) + (3/24) (1 + X_2 + X_2) + (6/24) (1 + X_2 + X_1 + X_1) + (1/24) (1 + X_1 + X_1+X_1+X_1)


X_4 = 1 + (1/4)X_4 + 8/24*4 + 3/24*5 + 6/24*3 + 1/24

Unless I'm mistaken this gives X_4 = 5.
OMG PRIMES! Just kidding. (Presumably.)

So for any given permutation of length n, you just break it up into all the cycles and add the values of the cycles. But if the permutation is actually an n-cycle, you have to do the computation I described above.

If you really have to do it this way though, N=1000 is going to be outside the realm of computation. In which case it would be nice if there were some cute counting argument that just told us that X_n is the (n+1)st Fibonacci number or something.

Edit: actually there is a small chance this could be it if we do something where you separate the permutations where n is fixed and isn't fixed. Need to think more.

Edit 2: Also can I ask what this is for?

I think it gives X_4 = 4 (just like I got with my calculation).

So X_4 = 4 and X_2 + X_2 = 2 + 2 = 4
I find this contra-intuitive? And could it be X_8 = X_2 * 4 = 8 and so on ...

It's a programming exercise I found somewhere on the web ...

Yep, you're right. And I'm pretty sure this gives X_5 = 5. I can't even do algebra today.

X_5 = 24/120(1+X_5) + 30/120(1+X_4) + 20/120(1+ X_3 + X_2) + 20/120(1+ X_3 + X_1 + X_1) + 15/120(1+ X_2 + X_2 + X_1) + 10/120(1+ X_2 + X_1 + X_1 + X_1) + 1/120(1)

In the long run it should be on the order of n since on average, you get to lock 1 element in place every time.

Yeah probably it has this easy/neat solution:

N=840 and 34 elements are on the correct position.
The solution is X_806 = 806