Continuing from the last Project Euler post I worked on the lexicographic permutations quiz in PowerShell. The problem being:
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
Spoiler Alert
To discover the answer I started with 1,2,3,4 and looked for patterns after manually completing this.
1234
1243
1324
1342
1423
1432
[… Continued with 2/3/4 which each have 6 permutations.]
The aha! moment came when I noticed that the total combinations in the first group of six (which uses combinations only of 2,3,4) is calculated by 1*2*3 = 6. Continuing to the full set of 24, I made sure the pattern worked. 1*2*3*4=24. It took some mental gymnastics to remember what this was, sure enough these are factorials and in notation are preceded with a exclamation point (i.e. 1*2*3*4 = !4). This is this foundation of this problem.
To figure this out on a large scale, quickly through an algorithm, the factorial of the numbers worked with (in this example: 1,2,3,4) is calculated. So !4 = 24. I then divided 24 by the total number of numbers (1,2,3,4) to get 6. This number is the interval at which the next number is used. For example lets plot out every sixth number in the pattern (by hand just for now after manually doing 24 quickly!).
6: 1432
12: 2431
18: 3421
24: 4321
You’ll see that the number at every sixth index is the last time it is used, 1 will never show up past 6th index, 3 will never show up after the 18th. This is a key part of using something that is not brute force. Looking for the 8th index? We can see that we are no longer in the 1’s for the first index group, but more importantly that we MUST use a 2. To find the next number, the process is repeated. We must make sure to update the index for the second run which repeats with numbers 1,3,4 so we take off 6 of the possibilities we just ruled out.
Confused? Hopefully this debugger output helps, looking for the 8th index which is 2143.
Total possible combinations 24. Using interval 6. Numbers being used: 1,2,3,4
Searching for index 86
12
18
24Group: 6 | Index: 1 | Digit: 2
Note: Group shows the outputted interval index which is below the index being searched (possibilities: 0,6,12,18). Index is the same as group, but is the actual index of the group. Digit shows what digit works for the first location. Notice how in the next run it is excluded from numbers being used!Total possible combinations 6. Using interval 2. Numbers being used: 1,3,4
Searching for index 22
4
6Group: 0 | Index: 0 | Digit: 1
Total possible combinations 2. Using interval 1. Numbers being used: 3,4
Searching for index 21
2Group: 1 | Index: 1 | Digit: 4
Total possible combinations 1. Using interval 1. Numbers being used: 3
Searching for index 11
Group: 0 | Index: 0 | Digit: 3
2143
This script took 0.0150009 sec(s) seconds to run
The full source code is included below:
function Get-Factorial([int]$value) { if($value -lt 0){ $result = 0 } elseif($value -le 1) { $result = 1 } else { $result = $value * (Get-Factorial($value - 1)) } return $result } function Get-Permutation([System.Collections.ArrayList]$nums, [int]$targetIndex){ $factorial = Get-Factorial $nums.Count; $factorialIter = 0; $factorialIndex = 0; $factorialInterval = $factorial / $nums.Count; Write-Host "Total possible combinations $factorial. Using interval $factorialInterval. Numbers being used: $($nums -join ',')" Write-Host "Searching for index $($targetIndex+1)`n" for($i = 1; $i -le $nums.Count; $i++){ $curInterval = $factorialInterval * $i; Write-Host $curInterval; #Check for match if($curInterval -le $targetIndex){ $factorialIter = $curInterval $factorialIndex = $i } else{ break; } } $match = [string]$nums[$factorialIndex]; Write-Host "`nGroup: $factorialIter | Index: $factorialIndex | Digit: $match `n`n"; #Recurse $nums.RemoveAt($factorialIndex); if($nums.Length -gt 0){ $match += Get-Permutation $nums ($targetIndex - $factorialIter); } return $match; } ################################################## $indexToFind = 1000000; Get-Permutation @(0,1,2,3,4,5,6,7,8,9) ($indexToFind-1)
No Comments
There are no comments related to this article.
Leave a Reply