2

我正在尝试编写 vb.net 代码以返回集合的唯一组合 我的集合包含 3 个不同的元素。我在这篇文章中找到了类似的帖子，但找不到任何 VB 解决方案来获得此结果

例子：

元素：1、2、3

{ 1, 2, 3}

结果必须是

1
2
3
12
13
23
123
...........
>...................

我，我试图通过使用以下代码来实现这一点

Function GetCombinations(ByVal depth As Integer, ByVal values As String()) As IEnumerable(Of String)
    If depth > values.Count + 1 Then Return New List(Of String)
    Dim result = New List(Of String)

    For i = 0 To depth - 1
        For y = 0 To values.Count - 1
            If i = 0 Then
                result.Add(values(y))
            Else
                result.Add(values(i - 1) + values(y))
            End If
        Next
    Next
    Return result
End Function

得到结果

Dim reslt = GetCombinations(4, data_array)

?reslt
Count = 12
    (0): "1"
    (1): "2"
    (2): "3"
    (3): "11"
    (4): "12"
    (5): "13"
    (6): "21"
    (7): "22"
    (8): "23"
    (9): "31"
    (10): "32"
    (11): "33"

提示：我使用数学并设法计算组合数。我可以用这个公式测试

例如，这个公式称为 nCr。这意味着在 n 个元素中，有多少种方法可以取 r 个元素与 r 的唯一组合。

nPr = n!/(n-r)!
n! = 1 * 2 * 3 * 4* ... (n-1) * n

Elements: 1, 2, 3
In this case n = 3 and r can be 1, 2, and 3 all

number of combinations  = 3P1 + 3P2 + 3P3
                                          = 3!/2! + 3!/1! + 3!/0!
                                          = 6/2 + 6/1 + 6/1                    (0!=1)
                                          = 3+6+6
                                          = 15
4

2 回答 2

1

了解该术语可以更轻松地找到现有算法。您正在寻找的是一个电源组。这是我在Rosetta Code上找到的 C# 实现的快速 VB.NET 翻译：

Public Function GetPowerSet(Of T)(ByVal input As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))
    Dim seed As IEnumerable(Of IEnumerable(Of T)) = {Enumerable.Empty(Of T)()}
    Return input.Aggregate(seed, Function(a, b) a.Concat(a.Select(Function(x) x.Concat({b}))))
End Function

测试：

For Each x In GetPowerSet({1, 2, 3})
    Console.WriteLine(String.Join(", ", x))
Next

输出：

1
2
1, 2
3
1, 3
2, 3
1, 2, 3

编辑- 根据您的最新解释，我认为您需要一种不同的方法。对于所有尺寸，直到输入尺寸，您似乎都想要与重复/替换的组合。对于从 1 到n的每个k值，您可以简单地使用参数(S, k)调用其中一个算法，并将所有结果连接到一组结果中。

翻译Python 的算法：

Public Iterator Function GetCombinationsWithReplacement(Of T)(source As IEnumerable(Of T), size As Integer) As IEnumerable(Of IEnumerable(Of T))
    Dim pool = source.ToList()
    Dim n = pool.Count
    If n = 0 AndAlso size > 0 Then
        Return
    End If
    Dim indices = Enumerable.Repeat(0, size).ToList()
    Yield indices.Select(Function(i) pool.Item(i))
    While True
        Dim index As Nullable(Of Integer) = Nothing
        For i = size - 1 To 0 Step -1
            If indices.Item(i) <> n - 1 Then
                index = i
                Exit For
            End If
        Next
        If Not index.HasValue Then
            Return
        End If
        indices = indices.Take(index.Value).Concat(Enumerable.Repeat(indices.Item(index.Value) + 1, size - index.Value)).ToList()
        Yield indices.Select(Function(i) pool.Item(i))
    End While
End Function

（如果您的 VB.NET 编译器不支持Yield ，则需要修改它。）

用不同大小调用它的结果是：

GetCombinationsWithReplacement({1, 2, 3}, 1)：

{1}
{2}
{3}

GetCombinationsWithReplacement({1, 2, 3}, 2)：

{1, 1}
{1, 2}
{1, 3}
{2, 2}
{2, 3}
{3, 3}

GetCombinationsWithReplacement({1, 2, 3}, 3)：

{1, 1, 1}
{1, 1, 2}
{1, 1, 3}
{1, 2, 2}
{1, 2, 3}
{1, 3, 3}
{2, 2, 2}
{2, 2, 3}
{2, 3, 3}
{3, 3, 3}

我们可以将它们加入一个包含所有 19 个子集的序列中：

Public Iterator Function GetCombinationsWithReplacementAllSizes(Of T)(source As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))
    Dim pool = source.ToList()
    For size = 1 To pool.Count
        For Each subset In GetCombinationsWithReplacement(pool, size)
            Yield subset
        Next
    Next
End Function
于 2013-08-24T16:06:08.090 回答
0

这里有一些可以帮助你的任意数量元素的伪代码（我没有声称这是最快的方法，它只是一种方法。）

  • 给定 elementList 是给定元素的列表
  • 给定 tempList 是一个列表作为临时持有者

  • 给定 resultList 是结果列表

    loop by # items in elementlist
{
  if tempList is empty  // special case for first iteration
    add each element of elementList to tempList and resultlist
  else
  {
    for each element in templist
      for each element2 in elementlist
        add combo to result list
    copy elements added to result list for this iteration to templist
  } 
}
于 2013-08-24T15:08:10.760 回答