WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
This problem, being one of the harder recent ones, tasks us with counting a certain type of permutations (we will call these valid). The constraint on permutations is that they should not contain any sub-permutation of type and contain at most sub-permutations of type ; where the containment is defined in the problem. In line with how the containment is defined, we will consider the permutations to be, informally, finite sequences of integers. We are supposed to count valid permutations for and which are of length at most . The single key realization that paves the path to a successful solution is that there are not that many valid permutations, and that they can be counted in a brute-force manner. This observation can be put into solid ground with the following claim:
Claim: Any valid permutation fixes all where .
Proof. Let be a valid permutation and be the largest integer to the right of which one can find a smaller integer in . Then, we can find in a subsequence:
where , , and all are smaller than . Since is a valid permutation and thus contains no sub-permutations of type , the integers must be in decreasing order. This means that contains at the very least these sub-permutations of type :
- All . There is of these.
- Any pair . There is of these. But again, since is valid, this gives us:
Coming back to how was defined, this means that for all , there are no smaller integers to the right of . From this, all must be fixed.
How does this help us to brute-force the solution? Well, there is going to be only a certain number of minimal valid prefixes consisting of (where the word minimal indicates that the prefix does not fix , and that all integers greater than will be necessarily fixed in a permutation with as prefix). Each such prefix will then contribute to the total result with valid permutations:
To construct all of the valid minimal prefixes, we can try all of the possible placements of the successive integers , recording any present sub-permutations to avoid having more than of them, recording occurrences of to avoid any containment of sub-permutation , and pruning wherever possible.
The following piece of Python code gives the answer in about 17 seconds, when run with PyPy.