独特的套装组合 [英] Unique Combination of Set

问题描述

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

I'm trying to write vb.net code to return unique combinations for set My set contains 3 different elements. I've found similar post this Post but couldn't find any VB solution to get this results

示例:

元素:1、2、3

{ 1, 2, 3}

结果必须是

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

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

i,m trying to achieve this by using following code

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"

提示:我使用数学并设法计算出没有组合.我可以测试出来这个公式

Hint: I work with Mathematics and manage to calculate no of combinations. i can test the out with this formula

示例有这个公式叫做 nCr.这意味着在 n 个元素中，有多少种方法可以采用 r 个元素与 r 的唯一组合.

Example there is this formula called nCr. it means out of n number of element how many way of taking r number of elements with unique combinations of 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 

推荐答案

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

Knowing the term makes it easier to find existing algorithms. What you're looking for is a power set. Here's a quick VB.NET translation of a C# implementation I found on Rosetta Code:

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

EDIT - 根据您的最新解释，我认为您需要一种不同的方法.似乎您想要与重复/替换的组合，适用于不超过输入尺寸的所有尺寸.您可以简单地为 k 从 1 到 n 的每个值调用带有参数 (S, k) 的其中一种算法，并加入所有结果成一组结果.

EDIT - Based on your latest explanation, I think you need a different approach. It seems you want combinations with repetitions / replacement, for all sizes up to the input size. You could simply call one of those algorithms with parameters (S, k) for each value of k from 1 to n and join all the results into a single set of results.

翻译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 编译器不支持 收益.)

(You will need to modify this if your VB.NET compiler doesn't support Yield.)

不同大小调用这个的结果是:

The results of calling this with different sizes are:

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 个子集的序列:

We can join these into a single sequence with all 19 subsets:

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

这篇关于独特的套装组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！