有没有更有效的方法来计算阵列的幂集? [英] Is there a more efficient way to calculate the power set of an array?

问题描述

这是我当前使用位的实现方式:

This is my current implementation using bits:

Function Array_PowerSet(Self)
    Array_PowerSet = Array()
    PowerSetUpperBound = -1
    For Combination = 1 To 2 ^ (UBound(Self) - LBound(Self)) ' I don't want the null set
        Subset = Array()
        SubsetUpperBound = -1
        For NthBit = 0 To Int(WorksheetFunction.Log(Combination, 2))
            If Combination And 2 ^ NthBit Then
                SubsetUpperBound = SubsetUpperBound + 1
                ReDim Preserve Self(0 To SubsetUpperBound)
                Subset(SubsetUpperBound) = Self(NthBit)
            End If
        Next
        PowerSetUpperBound = PowerSetUpperBound + 1
        ReDim Preserve Array_PowerSet(0 To PowerSetUpperBound)
        Array_PowerSet(PowerSetUpperBound) = Subset
    Next
End Function

请忽略对变体的滥用. Array_Push和Array_Size应该是不言自明的.

Please ignore the abuse of Variants. Array_Push and Array_Size should be self-explanatory.

以前，我为每个组合生成一个二进制字符串，但是涉及调用另一个效率不高的函数.

Previously, I was generating a binary string for each combination, but that involved calling another function which wasn't very efficient.

除了使用较少的Variants并在内部移动外部函数调用外，还有什么方法可以使它更有效?

Aside from using less Variants and moving external function calls inside, is there any way I can make this more efficient?

这是一个完全独立的版本.

Here's a fully independent version.

Function Array_PowerSet(Self As Variant) As Variant
    Dim PowerSet() As Variant, PowerSetIndex As Long, Size As Long, Combination As Long, NthBit As Long
    PowerSetIndex = -1: Size = UBound(Self) - LBound(Self) + 1
    ReDim PowerSet(0 To 2 ^ Size - 2) ' Don't want null set

    For Combination = 1 To 2 ^ Size - 1
        Dim Subset() As Variant, SubsetIndex As Long: SubsetIndex = -1

        For NthBit = 0 To Int(WorksheetFunction.Log(Combination, 2))
            If Combination And 2 ^ NthBit Then
                SubsetIndex = SubsetIndex + 1
                ReDim Preserve Subset(0 To SubsetIndex)
                Subset(SubsetIndex) = Self(NthBit)
            End If
        Next

        PowerSetIndex = PowerSetIndex + 1
        PowerSet(PowerSetIndex) = Subset
    Next

    Array_PowerSet = PowerSet
End Function

和测试:

Dim Input_() As Variant, Output_() As Variant, Subset As Variant, Value As Variant
Input_ = Array(1, 2, 3)
Output_ = Array_PowerSet(Input_)

For Each Subset In Output_
    Dim StringRep As String: StringRep = "{"

    For Each Value In Subset
        StringRep = StringRep & Value & ", "
    Next

    Debug.Print Left$(StringRep, Len(StringRep) - 2) & "}"
Next

推荐答案

由于子集的数量呈指数增长，因此即使您在做的事情上仍有改进的余地，没有一种算法是真正有效的:

Since the number of subsets grows exponentially, no algorithm is truly efficient, although there is room for improvement in what you are doing:

ReDim Preserve在用于将数组扩展为单个项目时效率低下，因为它需要创建一个具有1个以上空间的新数组，然后将旧元素复制到新数组中.最好预先分配足够的空间，然后将其缩小为大小:

ReDim Preserve, when used to extend an array by a single item, is inefficient since it involves creating a new array with 1 more space and then copying the old elements to the new array. It is better to pre-allocate enough space and then trim it down to size:

Function PowerSet(Items As Variant) As Variant
    'assumes that Items is a 0-based array
    'returns a 0-based jagged array of subsets of Items
    'where each subset is a 0-based array

    Dim PS As Variant
    Dim i As Long, j As Long, k As Long, n As Long
    Dim subset As Variant

    n = 1 + UBound(Items) 'cardinality of the base set
    ReDim PS(0 To 2 ^ n - 2)
    For i = 1 To 2 ^ n - 1
        subset = Array()
        ReDim subset(0 To n - 1)
        k = -1 'will be highest used index of the subset
        For j = 0 To n - 1
            If i And 2 ^ j Then
                k = k + 1
                subset(k) = Items(j)
            End If
        Next j
        ReDim Preserve subset(0 To k)
        PS(i - 1) = subset
    Next i
    PowerSet = PS
End Function

一个测试功能:

Sub test()
    Dim stuff As Variant, subsets As Variant
    Dim i As Long

    stuff = Array("a", "b", "c", "d")
    subsets = PowerSet(stuff)
    For i = LBound(subsets) To UBound(subsets)
        Cells(i + 1, 1).Value = "{" & Join(subsets(i), ",") & "}"
    Next i
End Sub

这篇关于有没有更有效的方法来计算阵列的幂集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！