String Permutations Simplified with PowerShell

Overview

Permutations are arrangements of elements in a specific order. In permutations, each element appears exactly once, and the order matters. For instance, given a set of elements, different permutations arise by rearranging these elements in distinct sequences, resulting in unique combinations.

The Mathematic Explanation

In the context of permutations, n typically represents the number of elements or items being permuted. It’s the size or cardinality of the set from which permutations are being generated. So, in the expression n!, n represents the number of elements in the set. The exclamation mark following a number, or a variable is called a factorial. If you’re not math savvy like me, this is a newer concept. If we are discussing string permutations, understanding factorials play a crucial role in because they represent the total number of possible arrangements of the string.

A Quick Example

I want to find all possible letter combinations of the word “cat”. I see the number of letters in the word “cat” is three. So, using our fancy new math tool, factorials, we can calculate the total number of letter combinations.

n = 3
n! = 6
We get 6 because
3 * 2 * 1 = 6

PowerShell Permutation Function

Here is a function Get-Permutations that outputs all permutations of a word to the terminal and a text file.

function Get-Permutations {
    [CmdletBinding()]
    param (
        [string] $prefix,
        [string] $word
    )
    if([string]::IsNullOrEmpty($word)){
        Write-Host $prefix -ForegroundColor Green
        Add-Content -Path $fileName -Value $prefix
    }else{

        for($i = 0; $i -lt $word.Length; $i++){
            $char = $word[$i]
            $newPrefix = $prefix + $char
            $newWord = $word.Substring(0, $i) + $word.Substring($i + 1)
            Write-Output("Character: {0} - Prefix: {1} - Word {2}" -f $char, $newPrefix, $newWord)
            Get-Permutations -prefix $newPrefix -word $newWord
        }
    }
}

$word = "gate"
$fileName = "$word-permutations.txt"

if( -not (Test-Path "$word-permutations.txt")){
    New-Item -ItemType File -path "$PSScriptRoot\$fileName"
}

Get-Permutations -prefix "" -word $word

PowerShell Permutation Function Explained

Using recursion, we test if the word we passed in is empty, then we have a valid letter combination, so we output it to the console and add the value to the text file.

If this condition is not met, we use a for loop with the number of iteration equal to $word.Length - 1. We take the character of the $word argument at index $i and add it to $prefix. We also get the $newWord at this iteration. Let’s look at an example if the iteration variable $i was equal to 2. It’s also good to learn how the SubString method works in PowerShell, because I found out the hard way that depending on what your project is, manipulating string is a common occurrence and there are many built-in tools to assist you.

$word.substring(0, $i) # Retrieve characters from word at index 0 to $i, but not including index $i

$word.substring($i + 1) # $retrieves all charaters at and after index $i + 1

$newWord = $word.substring(0, $i) + $word.substring($i + 1)

# and example at iteration 2, you can replace 2 with $i in the loop
"turtle"[2] = "r"
"turtle".Substring(0, 2) = "tu"
"turtle".Substring(2 + 1) = "tle"

Within the iteration, we recursively call the Get-Permutations function with the $newPrefix and $newWord values. When the $prefix length is equal to the $word length, we can output it to the terminal and append it to the text file. Let’s look at the output from permutation the three letter word “cat”.

cat
cta
act
atc
tca
tac

Conclusion

Although this is common knowledge in computer science, if you didn’t have the opportunity to take an algorithm class or aren’t catching on as quickly, other online resources are a good start. I wrote this blog so you can use it as an additional resource, and so I can better understand permutation. Maybe you can modify the code to use a while loop instead. If you have any suggestions to make this post better, please leave a comment or Contact Me.