Fun with PowerShell and Permutations

Somewhere a while back I was reading about working with trying to find all possible combinations of a given word, called Permutations. Since my main goal was to take a given word (or string) and cycle through all of the possible combinations, I figure this would make for a fun attempt at a PowerShell function.

I really don’t need to calculate the number of permutations, but just for the heck of it, I through something quick together to get the possible combinations. But first I had to figure out what the formula was to make this happen. In this case, I was aiming for a Permutation with no repetition. This means that each item in the string can only be used once, so if I chose “cat”, it can only have the “c”,”a” and “t” instead of possibly having all “c’s”, “a’s” and “t’s”. Knowing this, the formula that I needed consisted of this:

3!

I use a factorial with the number of characters in the string to determine how many permutations there are. An easier way to look at it is like this:

3*2*1

This gives me the answer of 6. So I know that there are 6 possible permutations to “cat”. My PowerShell approach is pretty primitive, but works just fine for me.

$string = "cat"
Invoke-Expression ($String.length..1 -join "*")

image

Like I said, nothing earth shattering here. The next step was to make my function to the permutation possible. I had seen others do this using a variety of languages from C#, java, etc… and figure if they can do this, the so can I in PowerShell.

In the end, I came up with a function on Get-StringPermutation that can take a string and show all possible permutations to it.

Get-StringPermutation -String "cat"

image

Larger strings can be piped into Format-Wide and specifying a column size to display everything.

Get-StringPermutation -String "super" | 
Format-Wide -Column 4

image

Of course, if you wanted to know how many permutations there were, you can do this:

$permutations = Get-StringPermutation -String "super"
$permutations.count

Of course, you could always pipe the output into Measure-Object as well to get the answer, which in the case of “super”, is 120.

The basics of the function include using a StringBuilder to add the String which allows for easier access to move each letter of the string around. That means that I can re-order all of the letters in the string to get all possible combinations.

There is definitely a ton of room for improvement on this code. Possible inclusions are allowing a collection of items to find all permutations or allowing for repetition as well.

The function can be downloaded from the Script Repository and I also have the source code available below to view as well. Check them both out and let me know what you think!

Download

http://gallery.technet.microsoft.com/scriptcenter/Get-StringPermutation-107c7a75

Source Code

Function Get-StringPermutation {
    <#
        .SYNOPSIS
            Retrieves the permutations of a given string. Works only with a single word.
 
        .DESCRIPTION
            Retrieves the permutations of a given string Works only with a single word.
       
        .PARAMETER String           
            Single string used to give permutations on
       
        .NOTES
            Name: Get-StringPermutation
            Author: Boe Prox
            DateCreated:21 Feb 2013
            DateModifed:21 Feb 2013
 
        .EXAMPLE
            Get-StringPermutation -String "hat"
            Permutation                                                                          
            -----------                                                                          
            hat                                                                                  
            hta                                                                                  
            ath                                                                                  
            aht                                                                                  
            tha                                                                                  
            tah        

            Description
            -----------
            Shows all possible permutations for the string 'hat'.

        .EXAMPLE
            Get-StringPermutation -String "help" | Format-Wide -Column 4            
            help                  hepl                  hlpe                 hlep                
            hpel                  hple                  elph                 elhp                
            ephl                  eplh                  ehlp                 ehpl                
            lphe                  lpeh                  lhep                 lhpe                
            leph                  lehp                  phel                 phle                
            pelh                  pehl                  plhe                 pleh        

            Description
            -----------
            Shows all possible permutations for the string 'hat'.
 
    #>
    [cmdletbinding()]
    Param(
        [parameter(ValueFromPipeline=$True)]
        [string]$String = 'the'
    )
    Begin {
        #region Internal Functions
        Function New-Anagram { 
            Param([int]$NewSize)              
            If ($NewSize -eq 1) {
                return
            }
            For ($i=0;$i -lt $NewSize; $i++) { 
                New-Anagram  -NewSize ($NewSize - 1)
                If ($NewSize -eq 2) {
                    New-Object PSObject -Property @{
                        Permutation = $stringBuilder.ToString()                  
                    }
                }
                Move-Left -NewSize $NewSize
            }
        }
        Function Move-Left {
            Param([int]$NewSize)        
            $z = 0
            $position = ($Size - $NewSize)
            [char]$temp = $stringBuilder[$position]           
            For ($z=($position+1);$z -lt $Size; $z++) {
                $stringBuilder[($z-1)] = $stringBuilder[$z]               
            }
            $stringBuilder[($z-1)] = $temp
        }
        #endregion Internal Functions
    }
    Process {
        $size = $String.length
        $stringBuilder = New-Object System.Text.StringBuilder -ArgumentList $String
        New-Anagram -NewSize $Size
    }
    End {}
}

About Boe Prox

Microsoft Cloud and Datacenter MVP working as a SQL DBA.
This entry was posted in powershell, scripts and tagged , . Bookmark the permalink.

One Response to Fun with PowerShell and Permutations

  1. Marc R Kellerman says:

    I created a function to use your function with an Array of words..

    This is my first public post of code that i’ve made.. so please be gentle on me!

    The limit of 75 items in the array is due to me using ASCII characters to represent each item in the array, and use your Get-StringPermutation to give me the list of the possible permutations, and return the permutations in array form.

    Let me know what you think!

    Function Get-ArrayPermutation
    {
    <#
    .SYNOPSIS
    Retrieves the permutations of a given array. Works only with arrays with max 75 items.

        .DESCRIPTION
            Retrieves the permutations of a given array. Works only with arrays with max 75 items.
    
        .PARAMETER String           
            Array with strings used to give permutations on
    
        .NOTES
            Name: Get-ArrayPermutation
            Author: Marc R Kellerman
            DateCreated:06 Feb 2015
            DateModifed:06 Feb 2015
    
        .EXAMPLE
            Get-ArrayPermutation "cat", "dog", "fish"
            Permutation                                                                                                                                                     
            -----------                                                                                                                                                     
            {cat, dog, fish}                                                                                                                                                
            {cat, fish, dog}                                                                                                                                                
            {dog, fish, cat}                                                                                                                                                
            {dog, cat, fish}                                                                                                                                                
            {fish, cat, dog}                                                                                                                                                
            {fish, dog, cat}          
    
            Description
            -----------
            Shows all possible permutations for the strings in the array.
    
        .EXAMPLE
            Get-ArrayPermutation "cat", "dog", "fish", "bird" | Format-Wide -Column 3            
            {cat, dog, fish, bird}     {cat, dog, bird, fish}     {cat, fish, bird, dog}                              
            {cat, fish, dog, bird}     {cat, bird, dog, fish}     {cat, bird, fish, dog}                              
            {dog, fish, bird, cat}     {dog, fish, cat, bird}     {dog, bird, cat, fish}                              
            {dog, bird, fish, cat}     {dog, cat, fish, bird}     {dog, cat, bird, fish}                              
            {fish, bird, cat, dog}     {fish, bird, dog, cat}     {fish, cat, dog, bird}                              
            {fish, cat, bird, dog}     {fish, dog, bird, cat}     {fish, dog, cat, bird}                              
            {bird, cat, dog, fish}     {bird, cat, fish, dog}     {bird, dog, fish, cat}                              
            {bird, dog, cat, fish}     {bird, fish, cat, dog}     {bird, fish, dog, cat}         
    
            Description
            -----------
            Shows all possible permutations for the strings in the array.
    
    #>
    [cmdletbinding()]
    Param(
        [parameter(ValueFromPipeline=$True)]
        $Array = @('cat', 'dog', 'fish')
    )
    Begin {
        If ($Array.Count -lt 2) { Return $Array }
        If ($Array.Count -gt 75) { Throw "Array is too big (MAX: 75)." }
    }
    Process {
    
        $String = [char[]](48..(48 + $Array.Count - 1)) -join ''
    
        Get-StringPermutation $String | % {
    
            $StringPermutation = $_.Permutation
            $Permutation = $StringPermutation[0..$StringPermutation.length] | % { $Array[$([byte][char]$_.ToString())-48] } 
            [PSCustomObject]@{Permutation=$Permutation}
    
        }
    
    }
    End {
    
    }
    

    }

    $Array = “cat”, “dog”, “fish”, “monkey”, “snake”, “horse”
    Get-ArrayPermutation $Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s