Calculating Power Sets with Loops

[Eclyps19]

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

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

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

[Hack]

Moved to the Math Forum

[Schatzy]

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

[Eclyps19]

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.

[soft903]

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

    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

    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

        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.

[soft903]

Hi,

Here is VB6 version

[Eclyps19]

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.