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 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}}.
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.
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 SubPublic 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 FunctionPublic 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 .