1
$\begingroup$

algorithm: a=[1,2,3.....n] for i in (1,n+1): j=rand(1,n+1): swap(a[i],a[j])

let us say that n=3: 132 213 231 these 3 are 5 times possible and 123 312 321 are 4 times possible....

similarly for n=4 2143 occurs maximum number of times = 15 times and 4231 and 4123 occurs min times i.e 8 times only....

i figured it out for n=1,2,3,4; but i am not able to figure out the permutation which is maximum possible and minimum possible.

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't see how this can be answered, since it's entirely dependent on the behaviour of the random number generator. $\endgroup$ – David Richerby Sep 9 '18 at 17:54
  • $\begingroup$ @DavidRicherby Assume that the PRNG is perfect. Note that to get a uniformly random permutation, rand(1,n+1) needs to be changed to rand(i,n+1). $\endgroup$ – Yuval Filmus Sep 12 '18 at 6:38
  • $\begingroup$ For $n \geq 5$, the unique answer is $n,1,2,3,\dots,n-1$, as experiments readily show. It shouldn't be too hard to figure out why. $\endgroup$ – Yuval Filmus Sep 12 '18 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.