Monthly Archives: October 2015

Reverse Lexicographical Permutation

Reverse Lexicographical Permutation Needed Before solving ProjectEuler Problem 41, I thought that I might need a way to generate a Reverse Lexicographical Permutation. I looked on the web to see if anyone had an algorithm that I could implement. After searching for a while, I could not find any solutions. What to do? Write my own algorithm but how? I had a look at my previous article that included a diagram of how to find lexicographical permutations. Why not take the existing algorithm and modify it Continue reading →

Memoization Pattern for Factorials

ProjectEuler Problem 34 turned out to be relatively simply but offers the opportunity to demonstrate how the memoization pattern can significantly reduce processing time. Let’s have a look at the problem. Problem 34 – Digit Factorials 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of the factorial of their digits. Note: as 1! = 1 and 2! = 2 are not sums they are Continue reading →

Domain Restriction

Limit Processing With a Domain Restriction This is an example of how a domain restriction can be applied to a brute force problem. Although the computational complexity of this problem is not very high, one or more domain restrictions can vastly reduce the processing required to obtain the solution. Problem 32 – Pandigital Products We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital. Continue reading →

Integer Partitions – Part 3

Integer Partitions Post Analysis Now that the Integer Partitions problem, Problem 31 Coin Sums, is solved what have I learnt from the experience? First, problems that appear to be intractable because I am not a professional mathematician are in fact solvable, not in all cases, but at least in some cases. I told my wife about this problem and her reaction was “How on earth would you solve that? I have no idea where to start.” Second, skipping the step of writing out an algorithm Continue reading →