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)を使用してこれらのアルゴリズムの 1 つを呼び出すだけで、すべての結果を 1 つの結果セットに結合できます。

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 に答える