Euleryx Problem 24 – Lexicographic Permutations
My workflow and macro:
Spoiler
Workflow:
Macro:
Answer: 2783915460
Last Week's Favourite Solution:
Tough call on last weeks solutions as lots of people followed a similar approach of starting with a generate rows, identifying the abundant numbers, then using an outer join to find the records of interest. In order to decide upon a winner I ran each workflow and found @Hub119's to be the quickest! The group by before the join massively reduced the records going into the join which ultimately lead to the fastest run time. (Shout out to @AncientPandaman too, I was unable to download their solution but based on the writeup it was a well optimised solution). Please find both solutions on page one of last week's post or click here.
Definitions
- Permutation: A permutation is an arrangement of characters, where the order matters, representing a specific sequence/way something can be arranged.
Mathematical Theory:
To examine this question more closely, lets first investigate permutations themselves and figure out, how many permutation there are, based on the size of a list.
Total Permutations:
To figure this out, lets take some examples:
With one number, “1”, it is trivial to say that there is 1 possible permutation.
With two numbers, “1,2” we know there are 2 potential permutations, {1,2} and {2,1}
With three numbers we have {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} making 6 potential permutations.
Another way to consider the potential permutations with 3 numbers is by fixing the first digit in position, then taking sub-sets. With the numbers “1,2 and 3” the potential sub-set combos, are as follows:
Fix “3” in position then use, “1,2”
Fix “1” in position then use, “2,3”
Fix “2” in position then use, “1,3”
As we already saw from the case where we had two numbers, we know that each of the pair of numbers above, has a potential 2 permutations. With 3, sub-sets of length 2, we then have 3 x 2 = 6 total permutations.
If we start with 4 numbers, “1,2,3,4” the potential number of permutations can be calculated in a similar way, fix one digit in place, then make a subset of the remaining 3 digits.
Fix “1”, Subset, “2,3,4”
Fix “2”, Subset, “1,3,4”
Fix “3”, Subset, “1,2,4”
Fix “4”, Subset, “1,2,3”
As we know the number of permutations for a list of 3 numbers = 6, we now know that the number of permutations for a list of 4 numbers, is just 4 x 6 = 24.
Generalising this rule, we can say that if we have a list of “n” numbers, the potential number of permutations is:
This can also be expresses as n factorial = n! So, we can conclude that the total number of possible permutations, in a list of “n” numbers can be expressed as n!
Lexicographical Permutations:
Moving on to the problem at hand, to identify a given permutation when arranged numerically. Taking the example of 4 numbers, “1,2,3,4”, lets try and identify the 10th permutation. This can be called k, or the “permutation of interest”. The way I’m going to tackle this will be by identifying one digit at a time.
1) Lets begin by writing out the problem, in the subsets of 3, like before. We know that the first 6 values will occur when the 1, is fixed in the first position, and the remaining 3 numbers are arranged in their 6 potential permutations.
Fix “1”, Subset, “2,3,4” (this will cover permutations 1-6)
Fix “2”, Subset, “1,3,4” (this will cover permutations 7-12)
Fix “3”, Subset, “1,2,4” (this will cover permutations 13-18)
Fix “4”, Subset, “1,2,3” (this will cover permutations 19-24)
It becomes clear that 2, is the first digit as we want the 10th permutation (and 10 falls between 7 and 12).
Another way to calculate this would be to do 10 divided by the number permutations in a list of 3 numbers, 6, to get the value 10/6 = 1.6666… which when we round up, to identify the second number in the list “2”, as the first digit.
2) Once we have fixed “2” in position, we only need to consider, “1,3,4”. Additionally, we know that when “2” is the first digit, the permutations fall in the range 7-12. Therefore, within the arrangement of the remaining 3 digits, we need to identify the 10-6 = 4th permutation. Following similar rules to above, we find that:
Fixing “1”, Subset “3,4” (this will cover permutations 1-2)
Fixing “3”, Subset “1,4” (this will cover permutations 3-4)
Fixing “4”, Subset “1,3” (this will cover permutations 5-6)
Again, we can use this information to conclude that the second digit, will be a 3.
3) Finally, left with just two numbers “1,4” we know we are looking for the 4-2 = 2nd permutation.
Fix “1”, Subset “4” (permutation 1)
Fix “4”, Subset “1” (permutation 2)
This allows us to conclude that the final two numbers are “4”, followed by “1”.
4) Putting all this information together, we identify the 10th permutation as: 2,3,4,1
Condensing the above steps down, we get the following steps:
- List all “n” numbers
- Calculate the first digit by finding the “Permutation of interest” divided by the number of permutations in the list of numbers of length n-1. And round up to the next integer. K / (n-1)!
- Update the list, and “Permutation of interest”.
Method:
1 First of all, we need to both generate the list of digits, we are trying to arrange, and input the target permutation. This input information is then ready to be fed into an iterative macro.
2 Inside the macro, the first step is to identify the position of each number, in the sorted list. Whilst this might need trivial for the first iteration, once we have already placed the first few digits, this step will prove its value.
3 Next, the count records, and Append tools were used to create a column, identifying the size of the list.
4 Now we get onto the main calculations. Firstly, the position in the list, of the next digit is identified using the formula discussed above.
Once the next digit is identified, we only need to consider the remaining digits (in this case 9). We know that the first permutation, which starts with a 2, will be the 725,761th permutation, so for the remaining digits, we only need to consider permutations from this point onwards. Hence, the permutation we are interested in for the remaining digits is 1,000,000 – 725,760 = 274,240. The formula tool is used to update the permutation column accordingly.
The sequence position is also added in here so that we can sort the digits correctly, once the macro has finished.
5 Filter out the digit identified, based on the [Digit Position] column from earlier.
6 Output the record from above, then feed the remaining records back via the loop output anchor, making sure to drop the calculated columns to reset the schema.
7 After running the records through the macro, thy are output as follows:
8 All that’s left is to sort by the sequence position, and then concatenate the digits.
9 If you want, you can go one step further and add interface tools to the canvas, to make this calculator into an Analytic app:
10 Submit your answer to the Project Euler Website!
Summary:
Permutations can seem daunting at first, however, before too long we were able to break the problem down be isolating one digit at a time. By approaching the problem in the way, we were able to arrive at a solution with relatively few tools.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
