How shall I implement this algo for larger numbers?

Question

1.00/5 (1 vote)

See more:

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.

What I have tried:

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?

Posted 9-Sep-18 6:21am

Spam291203

Updated 9-Sep-18 7:35am

Add a Solution

Comments

Spam291203 10-Sep-18 3:59am

Any help would be appreciated!

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

KarstenK · Answer 1 · 2018-09-09T07:35:00

Solution 1

For generating random numbers you can use the rand function. It should initialized before the first call with srand. Maybe you also look at this C++ tutorial when you need further basic knowledge.d

Brute force is mostly not best solution, so you should inform about the theory.

Good luck with your homework. It has the purpose that YOU learn more about that stuff.

Posted 9-Sep-18 7:35am

KarstenK

Comments

Spam291203 9-Sep-18 13:45pm

I think you got that question wrong. I didn't ask how to generate a random number.
The thing is to find out the permutation which has the minimum probability of being generated when choosing random numbers in a linear sort.
Check out these sites: https://blog.codinghorror.com/the-danger-of-naivete/

https://www.quora.com/Why-does-shuffling-array-by-iterating-over-it-and-swapping-it-with-a-random-element-between-0-to-the-last-element-of-the-array-not-produce-a-uniformly-distributed-shuffle

Check out the answer by Shanker S

I hope you understand what my homework exactly is!

KarstenK 10-Sep-18 8:51am

That definitly not a coding question (for what this forum is made), but some high level statistic problem.

Tip: provide your data as array and than develop code that works it out. Use pointers to arrays to avoid copying.

Is it your master work?

Spam291203 10-Sep-18 11:03am

Believe me, it is a coding question.

I don't what you refer to by master work!

Spam291203 10-Sep-18 11:06am

import operator

N = 10
P = []
for i in range(1, N + 1):
P += [i]
d = {}
for ind1 in range(N):
lv1 = P
lv1[0], lv1[ind1] = lv1[ind1], lv1[0]
for ind2 in range(N):
lv2 = lv1
lv2[1], lv2[ind2] = lv2[ind2], lv2[1]
for ind3 in range(N):
lv3 = lv2
lv3[2], lv3[ind3] = lv3[ind3], lv3[2]
for ind4 in range(N):
lv4 = lv3
lv4[3], lv4[ind4] = lv4[ind4], lv4[3]
for ind5 in range(N):
lv5 = lv4
lv5[4], lv5[ind5] = lv5[ind5], lv5[4]
for ind6 in range(N):
lv6 = lv5
lv6[5], lv6[ind6] = lv6[ind6], lv6[5]
for ind7 in range(N):
lv7 = lv6
lv7[6], lv7[ind7] = lv7[ind7], lv7[6]
for ind8 in range(N):
lv8 = lv7
lv8[7], lv8[ind8] = lv8[ind8], lv8[7]
for ind9 in range(N):
lv9 = lv8
lv9[8], lv9[ind9] = lv9[ind9], lv9[8]
for ind10 in range(N):
lv10 = lv9
lv10[9], lv10[ind10] = lv10[ind10], lv10[9]
s = " ".join(map(str, lv10))
if s in d:
d[s]+=1
else:
d[s]=1
d = sorted(d.items(), key=operator.itemgetter(1))
print(d[0])
print(d[-1])

This is the brute-force code I wrote for N=9. Any way to optimise this? The code is in Python btw!

Member 13979697 · Answer 2 · 2018-09-10T13:04:00

Solution 2

This is the problem from the online competition in codechef.com, it is the violations of the code of conduct of codechef

Posted 10-Sep-18 13:04pm

Member 13979697

Updated 10-Sep-18 13:35pm

Comments

Patrice T 10-Sep-18 20:52pm

Ca, you give link to contest ?