Add-ins:
Excel
PowerPoint

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 www.google.com, mathworld.wolfram.com, or www.wikipedia.org.

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 2^{n} elements where n is the
number of elements in *A*. It is typically denoted by *
P(A) *or *2 ^{A}*. Note that each element of a
power set is a set in itself. For example, the power set of
the set

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 n^{r}.

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)
Else
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)
Else
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)
Else
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 Else 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 http://groups.google.com/group/microsoft.public.excel.worksheet.functions/browse_frm/thread/8ac4a84b7df1ff97/5deaecfc5da1db8d

For more on newsgroups see Outlook Express & Newsgroups .