PowerShell and Project Euler 24: Lexicographic Permutations

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 8

6
12
18
24

Group: 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 2

2
4
6

Group: 0 | Index: 0 | Digit: 1

Total possible combinations 2. Using interval 1. Numbers being used: 3,4
Searching for index 2

1
2

Group: 1 | Index: 1 | Digit: 4

Total possible combinations 1. Using interval 1. Numbers being used: 3
Searching for index 1

1

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)