Problem 367

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Problem 367

Post by LarryBlake »

Problem 367 (View Problem)
1. It says that 3 elements are selected randomly and shuffled, with equal probability to all results. That means that the result could be the same position, right?

2. These lines are repeated in the wording:
The already sorted sequence will take 0 steps.
If we consider all permutations of the first 4 natural numbers as input the expectation value of the number of shuffles, averaged over all 4! input sequences is 27.5.
Does that refer to the "pick 2 and swap", the "pick 3 and shuffle", or both?
Image
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 367

Post by thundre »

LarryBlake wrote:Problem 367 (View Problem)
1. It says that 3 elements are selected randomly and shuffled, with equal probability to all results. That means that the result could be the same position, right?

2. These lines are repeated in the wording:
The already sorted sequence will take 0 steps.
If we consider all permutations of the first 4 natural numbers as input the expectation value of the number of shuffles, averaged over all 4! input sequences is 27.5.
Does that refer to the "pick 2 and swap", the "pick 3 and shuffle", or both?
1. Yes.

2. 27.5 is the answer for "pick 3 and shuffle". The answer for "pick 2 and swap" is given as 24.75.
Image
LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: Problem 367

Post by LarryBlake »

Ah. Thanks.
Image
AsdfUser
Posts: 1
Joined: Sun Mar 25, 2012 4:13 pm

Re: Problem 367

Post by AsdfUser »

Is 6200 (rounded) the correct result for the first 7 natural numbers?

Thank you in advance.
Image
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 367

Post by thundre »

Since 135 people have solved it, I guess it's OK to answer.

Yes, that is the correct value for 7.
Image
AlbPer85
Posts: 2
Joined: Sat Aug 18, 2012 10:24 pm

Re: Problem 367

Post by AlbPer85 »

I am still getting the wrong answer... :(
For the values 4 and 7 I have the correct answers (7 --> 6200, as in the previous post).
For the first 9, 10 and 12 natural numbers I get the solutions:

9 --> 441038
10 --> 4397120
11 --> "FORBIDDEN ;-)"
12 --> 578412917
Could someone tell me if this values are correct?
(I hope this is not a "spoiler").

Thank you in advance.
User avatar
Marcus_Andrews
Administrator
Posts: 1518
Joined: Wed Nov 09, 2011 5:23 pm

Re: Problem 367

Post by Marcus_Andrews »

They're all wrong, but close. You might just have a precision issue somewhere.
Image
AlbPer85
Posts: 2
Joined: Sat Aug 18, 2012 10:24 pm

Re: Problem 367

Post by AlbPer85 »

Thank you very much, Marcus.

In the end it was a silly mistake due to conversion from integer to double. Problem solved.
kingvash
Posts: 13
Joined: Sun Nov 22, 2009 2:57 am

Re: Problem 367

Post by kingvash »

EDIT:

Python numpy does not have quite the precision I would like. Switched to using sympy (which can do arbitrary precision) and all is well now!
MuthuVeerappanR
Posts: 483
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 367

Post by MuthuVeerappanR »

Taking E(n, k ) to be expected value in the case of permutation of 'n' numbers taking 'k' values at each step, Can someone verify these values??

E(2, 2) = 1
E(3, 2) = 9
E(4 , 2) = 49.5 (I know this is wrong goin by the example given in the problem)

E(3, 3) = 5
E(4, 3) = 27.5 (Surprisingly I get this right..)
E(5, 3) = 2969/20 = 148.45

E(4, 4) = 23
E(5, 4) = 373/33 = 124.3333
E(6, 4) = 54497/72 = 756.902777

I suspect I get wrong values only in case of k = 2. Any help is greatly appreciated.

EDIT: I even verified E(3, 2) by hand calculations. So I think that's correct too... Since it is also easy to verify E(n, n) = n! - 1, I suspect the other values are right too.. (unless someone says the given values are wrong..). I see only two possibilities here: Either the value given in the question is wrong (Very Very highly unlikely based on the time I've spent on Project Euler) or am misinterpreting something (relatively more likely) but I can't understand where am getting wrong..

Thanks.
Last edited by MuthuVeerappanR on Tue Apr 04, 2017 8:33 am, edited 2 times in total.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 367

Post by jaap »

MuthuVeerappanR wrote: Tue Apr 04, 2017 7:11 amI suspect I get wrong values only in case of k = 2. Any help is greatly appreciated.
I suspect that your k=2 case is that you pick two numbers, and randomly permute them, i.e. 50% that they swap and 50% that they don't. This makes your results twice what they should be if you always swap the two randomly chosen numbers.
MuthuVeerappanR
Posts: 483
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 367

Post by MuthuVeerappanR »

Oh... I get it.. Then the k = 2 example value is for 'Bozo sort' whereas the k = 3 example and the question is about a 'variation of Bozo sort'.

Thanks jaap for helping me reach my 325th problem... :)

I'll leave it to the admins to decide whether or not to delete the values I've given in the previous post..
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Post Reply