Vtyjkyuk

I have to create an Array A, and for the sake of making things clear, I will create A = [a,b,c,d] with length n, 4 in this case. Then I feed A to the following algorithm;

For i in 1...n: do
 generate a random number j
 Swap(A[i], A[j])

Now how do I come up with this array, call it A (array contents decided by me), so the probability that the new array generated by this algorithm after giving it A as input, is closest to A. So I have to create an Array, A, feed it to the algorithm and the result should be as close as possible to the original Array, A.

I assume that duplicates are not allowed. That is, the initial arrangement must be a permutation of the number $1,2,3,4.$ According to my calculations, it doesn't matter what the initial arrangement is, as indeed seems true intuitively.

Here's a python script to test this:

from itertools import permutations, product

for p in permutations(range(4)):
 a = list(p)
 count = 0
 for d in product(range(4), repeat=4):
 for i in range(4):
 a[i], a[d[i]], = a[d[i]], a[i]
 if a == list(p): count += 1
 print(p, count)

This produces the output

(0, 1, 2, 3) 10
(0, 1, 3, 2) 10
(0, 2, 1, 3) 10
(0, 2, 3, 1) 10
(0, 3, 1, 2) 10
(0, 3, 2, 1) 10
(1, 0, 2, 3) 10
(1, 0, 3, 2) 10
(1, 2, 0, 3) 10
(1, 2, 3, 0) 10
(1, 3, 0, 2) 10
(1, 3, 2, 0) 10
(2, 0, 1, 3) 10
(2, 0, 3, 1) 10
(2, 1, 0, 3) 10
(2, 1, 3, 0) 10
(2, 3, 0, 1) 10
(2, 3, 1, 0) 10
(3, 0, 1, 2) 10
(3, 0, 2, 1) 10
(3, 1, 0, 2) 10
(3, 1, 2, 0) 10
(3, 2, 0, 1) 10
(3, 2, 1, 0) 10

so in all cases the probability is the same: $10over4^4=0.0390625$

I'm sure that it can be proved that this is true for any $n:$ the initial permutation doesn't matter, although the technique escapes me. As a way to discover the proof, I suggest modifying the above script to print out the random numbers (d in the script) that leave the permutations fixed for two specific permutations, and trying to see how one sequence maps to the other. This will probably give you the pattern you need to prove.

For the new formulation, if all the elements of $A$ are distinct, all that matters is the number of elements in $A$. Shorter is better because there are less permutations to choose from. Before you run your algorithm you can permute the elements into any order you want. Now imagine the permuted one is $[1,2,3,ldots n]$. You have some probability to end with $[1,2,3,ldots n]$. That will be the same for any given length of $A$.