How shall I implement this for larger numbers?
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?
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 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!
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!
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
maybe i'll give you the whole solution ,i have generalised for minimum probability
Topic archived. No new replies allowed.