You are on the Home/Excel/Excel Tips/Power Set page
Web This Site

Powerset, Subset, and Combinations & Permutations

Introduction to sets, subsets, and the power set

This serves as a brief introduction to the subject of sets, subsets, power sets, and combinations & permutations.  By its very focus it is not meant to be thorough but more like a refresher.  For more search,, or

A set is the name for a collection of some number of elements.  Typically, the elements of the collection are not ordered amongst themselves and multiplicity (multiple entries) is ignored.  An example of a set containing the first four letters of the alphabet is A={a,b,c,d}.  Membership is denoted by a � A.  Since elements are not ordered, {a,b,c,d} is the same set as {c,a,d,b}.  By some conventions the empty element j is considered to be a member of every set.  The empty set, a set containing no elements is typically denoted by {} or F.

A subset, B, of a set, A, is a collection of elements such that each element in B is also a member of A. Conversely, A is the superset of B.  B is said to be a proper subset, denoted by B � A, if A contains elements not present in B.  Otherwise, one writes B � A.  Examples of subsets of the set {a,b,c,d} are {a,b}, {c,d}, and {b,c,d}.  Two extreme examples are the empty set B={j} and the set B={a,b,c,d} containing all elements in A.

The number of subsets each containing r elements from a set containing n elements is given by n!/[r!(n-r)!] where x! is the factorial of x given by 1*2*3...*(x-1)*x.  The corresponding Excel function is COMBIN.

The power set of a set A is the set containing all possible subsets of A including the empty subset.  It contains 2n elements where n is the number of elements in A.  It is typically denoted by P(A) or 2A.  Note that each element of a power set is a set in itself.  For example, the power set of the set A={a,b,c,d} is the set P(A)={{}, {a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}}.

Introduction to combinations and permutations

A combination is a collection of r elements without regard to order taken from a collection of n elements.  Consequently, a combination is the same as a subset of size r.  Consequently, the number of possible combinations is given by n!/[r!(n-r)!] or the Excel function COMBIN.

A permutation is a collection of r elements from a collection of n elements keeping track of their order.  The number of permutations without repetition of an element is given by n!/(n-r)! and with repetition is given by nr.

Visual Basic for Applications code

The code below supports 4 public entry points (createSubset, createPowerSet, createPermutations, and createCombinations) for use by other code and 4 user defined functions or UDFs (UDFSubset, UDFPowerSet, UDFPermutations, and UDFCombinations).  In its current form the code does not handle data errors gracefully and may either fault or return erroneous results.  Also note that the functions createCombinations and UDFCombinations are added simply for the sake of completeness.  They are pass through functions and call the functions createSubset and UDFSubset respectively and are otherwise completely untested.

Option Explicit
Option Base 0
    Private Function NbrElements(Arr) As Integer
       On Error Resume Next
       NbrElements = UBound(Arr) - LBound(Arr) + 1
        End Function
    Private Function fixInput(Arr)
        If Not (TypeOf Arr Is Range) Then
            fixInput = Arr
        ElseIf Arr.Rows.Count > 1 Then
            fixInput = Application.WorksheetFunction.Transpose(Arr.Value)
            fixInput = Arr.Value
            End If
        End Function
    Private Function createOutput(Arr)
        If Not (TypeOf Application.Caller Is Range) Then
            createOutput = Arr
        ElseIf Application.Caller.Rows.Count > 1 Then
            createOutput = Application.WorksheetFunction.Transpose(Arr)
            createOutput = Arr
            End If
        End Function
Private Sub aSubset(Arr, CurrIdx, NbrItems, ByVal Delim As String, _
        ByVal PreString As String, ByRef Rslt)
    Dim i As Integer
    If NbrItems = 0 Then
        If PreString = "" Then Rslt(UBound(Rslt)) = PreString _
        Else Rslt(UBound(Rslt)) = Left(PreString, Len(PreString) - Len(Delim))
        ReDim Preserve Rslt(UBound(Rslt) + 1)
        For i = CurrIdx To NbrElements(Arr) - NbrItems + LBound(Arr)
            aSubset Arr, i + 1, NbrItems - 1, Delim, _
                PreString & Arr(i) & Delim, Rslt
            Next i
        End If
    End Sub
Public Function createSubset(Arr, NbrItems As Integer, Delim As String)
    Dim Rslt
    ReDim Rslt(0)
    aSubset Arr, LBound(Arr), NbrItems, Delim, "", Rslt
    ReDim Preserve Rslt(UBound(Rslt) - 1)
    Debug.Assert NbrElements(Rslt) = _
        Application.WorksheetFunction.Combin(NbrElements(Arr), NbrItems)
    createSubset = Rslt
    End Function
Public Function createPowerSet(Arr, Delim As String)
    Dim i As Integer, j As Integer, DestIdx As Integer, _
        Rslt, aSubset
    ReDim Rslt(0): DestIdx = 0
    For i = 0 To NbrElements(Arr)
        aSubset = createSubset(Arr, i, Delim)
        ReDim Preserve Rslt(UBound(Rslt) + NbrElements(aSubset))
        For j = LBound(aSubset) To UBound(aSubset)
            Rslt(DestIdx) = aSubset(j)
            DestIdx = DestIdx + 1
            Next j
        Next i
    ReDim Preserve Rslt(UBound(Rslt) - 1)
    createPowerSet = Rslt
    End Function
Private Sub AllPermutations(SrcData As Variant, ByVal RepetitionsOK As Boolean, _
        AlreadyUsed() As Boolean, ByVal RsltSize As Integer, _
        ByVal CurrentRslt, ByRef RsltArr(), Delim As String)
    If NbrElements(CurrentRslt) = RsltSize Then
        If NbrElements(RsltArr) = 0 Then ReDim RsltArr(0) _
        Else ReDim Preserve RsltArr(UBound(RsltArr) + 1)
        RsltArr(UBound(RsltArr)) = Join(CurrentRslt, Delim)
        Exit Sub
        End If
    Dim I As Integer
    If NbrElements(CurrentRslt) = 0 Then ReDim CurrentRslt(0) _
    Else ReDim Preserve CurrentRslt(UBound(CurrentRslt) + 1)
    For I = LBound(SrcData) To UBound(SrcData)
        If RepetitionsOK Then
            CurrentRslt(UBound(CurrentRslt)) = SrcData(I)
            AllPermutations SrcData, RepetitionsOK, AlreadyUsed, RsltSize, CurrentRslt, RsltArr, Delim
        ElseIf AlreadyUsed(I) Then
            AlreadyUsed(I) = True
            CurrentRslt(UBound(CurrentRslt)) = SrcData(I)
            AllPermutations SrcData, RepetitionsOK, AlreadyUsed, RsltSize, CurrentRslt, RsltArr, Delim
            AlreadyUsed(I) = False
            End If
        Next I
    End Sub

Public Function createPermutations(Arr As Variant, ByVal RsltSize As Integer, _
        ByVal RepetitionsOK As Boolean, ByVal Delim As String)
        'Arr, though declared as a variant should be an array.
    Dim CurrentRslt(), RsltArr(), AlreadyUsed() As Boolean
    ReDim AlreadyUsed(UBound(Arr))
    AllPermutations Arr, RepetitionsOK, AlreadyUsed, RsltSize, CurrentRslt, RsltArr, Delim
    createPermutations = RsltArr
    End Function
Public Function createCombinations(Arr, NbrItems As Integer, Delim As String)
    createCombinations = createSubset(Arr, NbrItems, Delim)
    End Function
Public Function UDFSubset(Arr, NbrItems As Integer, Delim As String)
    Arr = fixInput(Arr)
    UDFSubset = createOutput(createSubset(Arr, NbrItems, Delim))
    End Function
Public Function UDFPowerSet(Arr, Delim As String)
    Arr = fixInput(Arr)
    UDFPowerSet = createOutput(createPowerSet(Arr, Delim))
    End Function
Public Function UDFPermutations(Arr, RsltSize As Integer, _
        Optional RepetitionsOK As Boolean = True, Optional Delim As String = ",")
    Arr = fixInput(Arr)
    UDFPermutations = createOutput(createPermutations(Arr, RsltSize, RepetitionsOK, Delim))
    End Function
Public Function UDFCombinations(Arr, NbrItems As Integer, _
        Optional Delim As String = ",")
    UDFCombinations = UDFSubset(Arr, NbrItems, Delim)
    End Function


Myrna Larson has also shared code on this subject.  For her take on the subject, see 

For more on newsgroups see Outlook Express & Newsgroups