Unique Combos from powershell array - No duplicate combos

Question

I'm trying to figure out the best way to get unique combinations from a powershell array. For instance, my array might be

@(B,C,D,E)

I would be hoping for an output like this :

B
C
D
E
B,C
B,D
B,E
C,D
C,E
D,E
B,C,D
C,D,E
B,C,D,E

I do not want re-arranged combos. If combo C,D exists already then I do not want combo D,C. It's redundant for my purposes.

I looked into the functions here : Get all combinations of an array

But they aren't what I want. I've been working on figuring this out myself, but have spent quite a bit of time without success. I thought I'd ask the question here so that if someone else already know I'm not wasting my time.

Thanks!

Answer 1

This is an adaptation from a solution for a C# class I took that asked this same question. For any set find all subsets, including the empty set.

function Get-Subsets ($a){
    #uncomment following to ensure only unique inputs are parsed
    #e.g. 'B','C','D','E','E' would become 'B','C','D','E'
    #$a = $a | Select-Object -Unique
    #create an array to store output
    $l = @()
    #for any set of length n the maximum number of subsets is 2^n
    for ($i = 0; $i -lt [Math]::Pow(2,$a.Length); $i++)
    { 
        #temporary array to hold output
        [string[]]$out = New-Object string[] $a.length
        #iterate through each element
        for ($j = 0; $j -lt $a.Length; $j++)
        { 
            #start at the end of the array take elements, work your way towards the front
            if (($i -band (1 -shl ($a.Length - $j - 1))) -ne 0)
            {
                #store the subset in a temp array
                $out[$j] = $a[$j]
            }
        }
        #stick subset into an array
        $l += -join $out
    }
    #group the subsets by length, iterate through them and sort
    $l | Group-Object -Property Length | %{$_.Group | sort}
}

Use like so:

PS C:>Get-Subsets @('b','c','d','e')

b
c
d
e
bc
bd
be
cd
ce
de
bcd
bce
bde
cde
bcde

Note that computational costs go up exponentially with the length of the input array.

Elements     SecondstoComplete
15               46.3488228
14               13.4836299
13                3.6316713
12                1.2542701
11                0.4472637
10                0.1942997
 9                0.0867832

Answer 2

My tired attempt at this. I did manage to get it to produce the expected results but how it does it is not as elegant. Uses a recursive functionality.

Function Get-Permutations{
    Param(
        $theInput
    )
    $theInput | ForEach-Object{

        $element = $_
        $sansElement = ($theInput | Where-Object{$_ -ne $element})

        If($sansElement.Count -gt 1){
            # Build a collection of permutations using the remaining elements that were not isolated in this pass.
            # Use the single element since it is a valid permutation 
            $perms = ,$element
            For($elementIndex = 0;$elementIndex -le ($sansElement.Count - 1);$elementIndex++){
              $perms += ,@(,$element + $sansElement[0..$elementIndex] | sort-object)
            }

            # For loop does not send to output properly so that is the purpose of collecting the results of this pass in $perms
            $perms

            # If there are more than 2 elements in $sansElement then we need to be sure they are accounted for 
            If($sansElement -gt 2){Get-Permutations $sansElement}
        } 

    }
}

Get-Permutations B,C,D,E | %{$_ -join ","} | Sort-Object -Unique

I hope I can explain myself clearly....So each pass of the function will take an array. Each individual element of that array will be isolated from the rest of the array which is represented by the variables $element and $sansElement.

Using those variables we build individual and progressively larger arrays composing of those elements. Let this example show using the array 1,2,3,4

1
1,2
1,2,3
1,2,3,4

The above is done for each "number"

2
2,1
2,1,3
2,1,3,4

and so forth. If the returned array contains more that two elements (1,2 would be the same as 2,1 in your example so we don't care about pairs beyond one match) we would take that array and run it through the same function.

The real issue is that the logic here (I know this might be hard to swallow) creates several duplicates. I suppose you could create a hashtable instead which I will explore but it does not remove the logic flaw.

Regardless of me beating myself up as long as you don't have thousands of elements the process would still produce results.

Get-Permutations would return and array of arrays. PowerShell would display that one element per line. You asked for comma delimited output which is where -join comes in. Sort-Object -Unique takes those sorted string an discards the duplicates.

Sample Output

B
B,C
B,C,D
B,C,D,E
B,C,E      #< Missing from your example output.
B,D
B,D,E      #< Missing from your example output. 
B,E
C
C,D
C,D,E
C,E
D
E