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

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?

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.

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

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.

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.