1

I faced this problem on a website and I quite can't understand the output, please help me understand it :-

Bogosort, is a dumb algorithm which shuffles the sequence randomly until it is sorted. But here we have tweaked it a little, so that if after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle we get (1, 2, 5, 4, 3, 6) we will keep 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm. Calculate the expected amount of shuffles for the improved algorithm to sort the sequence of the first n natural numbers given that no elements are in the right places initially.

Input:

2
6
10

Output:

2
1826/189
877318/35343

For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions. I just can't understand the output.

asked Jun 17, 2012 at 9:58
0

1 Answer 1

1

You're working with a stochastic algorithm, the requested output is the expected value E[X] of the number of shuffles X needed to sort the vector (which is random at any given try).

Given an input vector of size N with no numbers in their place (they don't give you the vector because it can be shown that E[X] is the same for all vectors of N numbers with this property), which can be "Bogosorted" in k different ways, each way with Si shuffles and with the probability of appearance Pi, then E[X] = sum(Pi * Si)/sum(Pi) where the sum is taken over all possible ways the vector can be sorted this way (obviously, sum(Pi) = 1 so it's actually E[X] = sum(Pi * Si)).

Bring the E[X] fraction down to irreducible, and there's your output.

answered Jun 17, 2012 at 10:32
3
  • @vksi : could you please be more clear, elaborate ? Commented Jun 17, 2012 at 11:55
  • @Aaditya: I... really don't see how. You need to calculate Si and Pi, and do that sum, but I think that's the point of the problem. Do you want us to solve your problem? Commented Jun 17, 2012 at 12:01
  • math.stackexchange.com/questions/20658/… is the answer I think Commented Jun 17, 2012 at 12:02

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.