Calculating Power Sets with Loops

Okay, I don't know how many of you are big into math, but I'm making a program to calculate power sets with up to 5 elements. I basically have an array of 5 text boxes (index 0 to 4). The user can type in the number of elements they have, and then type an element in each text box.

If you don't know what a power set is, it basically finds every possible combo of elements within the set and outputs them to a list (including the full set, as well as the empty set).

For example, the power set of {1,2,3} is {1},{2},{3},{1,2},{2,3},{1,3},{},{1,2,3}

I achieved this output by using nested for loops.

I start with a simple for loop

Code:

---

for i = 0 to maxEl.text

list1.additem ("{" & text1(i).text & "}")

next

---

this grabs all combos of only 1 element. I then move on to 2 combined elements

Code:

---

for i = 0 to maxEl.text

for j = i+1 to maxEl.txt

list1.additem ("{" & text1(i).text & "," & text1(j).text & "}")

next

next

---

I keep adding nested for loops for more numbers.

Finally, I add the entire set, as well as the empty set "{}" to the end of the list.

This all works fine and dandy. My next task, the one I'm having trouble with, is exponential power sets. For example, the power set of a power set of a power set. Do any of you have an idea of how I would tackle this? Everything is saved in a listbox, so it's essentially in an array. If anyone has any ideas, please let me know.

Thanks

Moved to the Math Forum

can you give me an example of how an exponential power set would work by hand?

hmmm i can certainly try. I'm not positive this would be the correct answer, but I'll give it a go.

P(P(d))

if d = {x}, i'll get the following for P(d)

{x},{}

now I want to take the power of that so I'd get {x}, {}, {{x}, {}}

and so on.

Hi,

I think P(P(d)) , where d= {x} , should be
{}, {{}}, {{x}}, {{},{x}}

My idea is
find all set with 0 to n element, where n is the length of input

finding 0 and 1 element set is simply.

for all 2-element set, as you did, fix the "1st" then loop the "2nd"
for all 3-element set, would be fix the "1st" then add all 2-element but without repeat the "1st".
the general idea is same, fix "1st" then loop the rest

Code:

---

    Private Function PowerSet(ByVal aryInput As String()) As String()

        Dim Result As String() = {}
        Dim aryTemp As String() = Nothing
        Dim cnt As Integer = 0

        Try

            For i As Integer = 0 To aryInput.Length
                aryTemp = PowerSetPart(i, aryInput)

                ReDim Preserve Result(Result.Length - 1 + aryTemp.Length)
                For j As Integer = 0 To aryTemp.Length - 1
                    Result(cnt) = "{" & aryTemp(j) & "}"
                    cnt += 1
                Next
            Next

        Catch ex As Exception

            Debug.Print("ERROR in PowerSet: " & ex.ToString)

        End Try

        Return Result

    End Function

---

Code:

---

    Private Function PowerSetPart(ByVal intLength As Integer, ByVal aryInput As String()) As String()
        Dim Result As String() = {}

        Dim cnt As Integer = 0
        Dim cnt2 As Integer = 0
        Dim aryTemp As String() = Nothing
        Dim aryAdd As String() = Nothing

        Try
            If intLength = 0 Then

                ReDim Result(0)
                Result(0) = ""

            ElseIf intLength = 1 Then

                Result = aryInput

            Else

                For i As Integer = 0 To aryInput.Length - intLength

                    cnt2 = 0
                    ReDim aryTemp(aryInput.Length - i - 2)
                    For j As Integer = i + 1 To aryInput.Length - 1
                        aryTemp(cnt2) = aryInput(j)
                        cnt2 += 1
                    Next

                    aryAdd = PowerSetPart(intLength - 1, aryTemp)

                    ReDim Preserve Result(Result.Length - 1 + aryAdd.Length)
                    For j As Integer = 0 To aryAdd.Length - 1
                        Result(cnt) = aryInput(i) & "," & aryAdd(j)
                        cnt += 1
                    Next

                Next

            End If

            Return Result

        Catch ex As Exception

            Debug.Print("ERROR in PowerSetPart: " & ex.ToString)
            Return Nothing

        End Try

    End Function

---

Code:

---

        Dim aryTest As String() = {"1"}
        Dim aryTemp As String() = Nothing
        aryTemp = PowerSet(PowerSet(aryTest))

        Debug.Print("Length : " & CStr(aryTemp.Length))

        For i As Integer = 0 To aryTemp.Length - 1
            Debug.Print(aryTemp(i))
        Next

---

Edited: Just find that seem you are working with VB6, but my code is in VB2005. I would try to convert in VB6, though idea would be same.

Hi,

Here is VB6 version

Ah excellent. I'll have to try that out when I get home.

I am also a .NET programmer, but when I need to whip something up that's not too important I do vb6. I suppose it'd run a heck of a lot faster in .NET though :(


Thanks a lot. I'll let you know how it goes.