## 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

Don't post any spoilers
LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

### Problem 367

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? thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Problem 367

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. LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

### Re: Problem 367

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

### Re: Problem 367

Is 6200 (rounded) the correct result for the first 7 natural numbers? thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Problem 367

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

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

### Re: Problem 367

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").

Marcus_Andrews
Posts: 1518
Joined: Wed Nov 09, 2011 5:23 pm

### Re: Problem 367

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

### Re: Problem 367

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

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

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. It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 367

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.
Jaap's Puzzle Page MuthuVeerappanR
Posts: 483
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

### Re: Problem 367

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.. It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.