Project Euler Progress

I've been working through the problems on Project Euler and as I was making notes anyway I thought I'd put them in a log, on the web, hence this blog. If it serves no other purpose it will be somewhere to jog my memory on the things I've learned.

Project Euler (in case you haven't clicked on the link above) is a good way to exercise your programming chops. The problems are maths based but generally can't be solved with pen and paper as they involve too much work. For example, the first problem is "Find the sum of all multiples of 3 or 5 below 1000", and a simple C++ solutions is:

 int total = 0;
 for (int i=0; i<1000; i++) {
  if ((i%3==0) || (i%5==0)) {
   total += i;
  }
 }
 cout << "Answer is " << total << endl;

They get progressively more difficult from there but the emphasis stays on algorithms as opposed to mathematics.

To get started, here's my solution to Problem 24.


What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
I began by thinking about the simple case of the permutations of the digits 0, 1, and 2, let's say we want to find the fourth permutation. There are 3! (i.e. 6) elements in the list, and listed in lexicographic order they are:

012, 021, 102, 120, 201, 210

We can split the list into three sub-sections: two elements beginning with 0, two beginning with 1, and two beginning with 2. It's easy to see that the fourth element in the list is in the second of these sub-sections. Stated in terms of a zero indexed array: position 3 in the array is in position 1 of the array of sub-sections. We can use the size of these sub-sections, 2!, to calculate this result as 3/2! = 1 (because integers are truncated after division this works when the numbers don't divide evenly). The elements in this sub-sections start with the digit 1 and so the first digit of the answer is a 1.

Now we descend into the sub-section 102, 120. We just need to remove the digit 1 from the list of digits we're considering, recalculate the number of elements in this sub-section, and recalculated the position of our answer in this sub-section, then we can repeat the process until we've got the answer. The array is one element shorter than before so the new size is 2!. We can essentially discount all sub-sections before the one we're now in so the new position is the previous position minus 2!*1. Repeating the process brings us to the fourth element, 120.

This 3 digit example is trivial but the algorithm can be applied to a list with an arbitrary number of digits. Here's the C++ code to find the 1,000,000th lexicographic permutation of the digits 0 to 9:

auto pos = 999999; // 1,000,000th position, zero indexed
uint numDigits = 10;
vector<uint> digits(numDigits);
emuint n = 0;
generate(digits.begin(), digits.end(), [&n](){return n++;});

cout << "Answer is ";
for (uint i=numDigits; i>1; i--) {
  uint nextDigit = pos/Factorial(i-1);
  cout << digits[nextDigit];
  digits.erase(digits.begin()+nextDigit);
  pos -= nextDigit*Factorial(i-1);
}
cout << digits[0] << endl;




Note, this uses a factorial function, like one you could find here.