How shall I implement this for larger numbers?

[spam291203]

Consider the following algorithm, which generates a (not necessarily uniformly) random permutation of numbers 1 through N:

P := [1, 2, ..., N]
for i in 1..N do
j := rand(1, N)
swap(P[i], P[j])
Here, rand(1, N) returns a uniformly random integer between 1 and N inclusive. Let's denote the probability that the permutation generated by this algorithm is P by p(P).

Find a permutation P1 such that p(P1) is maximum possible and a permutation P2 such that p(P2) is minimum possible.

I brute-forced it till N=7 and answering using precalculation but for larger N (N<=17) ot gets stuck. O(N^17)!

How can I implement this code?

Else, is there any formula to calculate the probability that a number ends at a particular index in a non-uniform linear shuffle?

[kbw]

Yes.

Don't write code, work thru the first few on paper, and generalize.

[spam291203]

@kbw Could you help me in generalizing?

I have generalised the pattern for min p(P) but can't find a pattern in the maximum sequence.

I have also sent you a PM!

[wowisay]

@spam291203 how have you generalized for minimum

[ffloyd]

plzz give me the output for n=4,n=5,n=6
maybe i'll give you the whole solution ,i have generalised for minimum probability