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