如何生成一个列表的要素的组合 在.NET 4.0中 如何生成一个列表的要素的组合 在.NE

我有一个问题类似，但不完全相同的人回答在这里。

我想一个函数生成的所有元素的k个-combinations从n个元素的列表。 请注意，我要寻找的组合，而不是排列，而且我们需要改变为k的溶液（即硬编码的循环是一个禁忌）。

我要寻找一个解决方案，是一个）优雅，和b）可在VB10 / .NET 4.0进行编码。

这意味着a）要求LINQ解决方案是确定，b）中的那些使用C＃“产量”命令都没有。

组合的顺序并不重要（即，辞书，格雷码，什么具备的，你）和优雅的优于性能，如果两者有冲突。

（OCaml的和C＃解决方案， 这里将是完美的，如果他们能在VB10进行编码。）

Answer 1:

代码在C＃，产生的组合为k个元素的数组的列表：

public static class ListExtensions
{
    public static IEnumerable<T[]> Combinations<T>(this IEnumerable<T> elements, int k)
    {
        List<T[]> result = new List<T[]>();

        if (k == 0)
        {
            // single combination: empty set
            result.Add(new T[0]);
        }
        else
        {
            int current = 1;
            foreach (T element in elements)
            {
                // combine each element with (k - 1)-combinations of subsequent elements
                result.AddRange(elements
                    .Skip(current++)
                    .Combinations(k - 1)
                    .Select(combination => (new T[] { element }).Concat(combination).ToArray())
                    );
            }
        }

        return result;
    }
}

这里使用集合初始化语法是VB 2010（可用源 ）。

Answer 2:

我试图创建一个可以在VB中完成此任务的枚举。 这是结果：

Public Class CombinationEnumerable(Of T)
Implements IEnumerable(Of List(Of T))

Private m_Enumerator As CombinationEnumerator

Public Sub New(ByVal values As List(Of T), ByVal length As Integer)
    m_Enumerator = New CombinationEnumerator(values, length)
End Sub

Public Function GetEnumerator() As System.Collections.Generic.IEnumerator(Of List(Of T)) Implements System.Collections.Generic.IEnumerable(Of List(Of T)).GetEnumerator
    Return m_Enumerator
End Function

Private Function GetEnumerator1() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
    Return m_Enumerator
End Function

Private Class CombinationEnumerator
    Implements IEnumerator(Of List(Of T))

    Private ReadOnly m_List As List(Of T)
    Private ReadOnly m_Length As Integer

    ''//The positions that form the current combination
    Private m_Positions As List(Of Integer)

    ''//The index in m_Positions that we are currently moving
    Private m_CurrentIndex As Integer

    Private m_Finished As Boolean


    Public Sub New(ByVal list As List(Of T), ByVal length As Integer)
        m_List = New List(Of T)(list)
        m_Length = length
    End Sub

    Public ReadOnly Property Current() As List(Of T) Implements System.Collections.Generic.IEnumerator(Of List(Of T)).Current
        Get
            If m_Finished Then
                Return Nothing
            End If
            Dim combination As New List(Of T)
            For Each position In m_Positions
                combination.Add(m_List(position))
            Next
            Return combination
        End Get
    End Property

    Private ReadOnly Property Current1() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return Me.Current
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext

        If m_Positions Is Nothing Then
            Reset()
            Return True
        End If

        While m_CurrentIndex > -1 AndAlso (Not IsFree(m_Positions(m_CurrentIndex) + 1)) _
            ''//Decrement index of the position we're moving
            m_CurrentIndex -= 1
        End While

        If m_CurrentIndex = -1 Then
            ''//We have finished
            m_Finished = True
            Return False
        End If
        ''//Increment the position of the last index that we can move
        m_Positions(m_CurrentIndex) += 1
        ''//Add next positions just after it
        Dim newPosition As Integer = m_Positions(m_CurrentIndex) + 1
        For i As Integer = m_CurrentIndex + 1 To m_Positions.Count - 1
            m_Positions(i) = newPosition
            newPosition += 1
        Next
        m_CurrentIndex = m_Positions.Count - 1
        Return True
    End Function

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        m_Finished = False
        m_Positions = New List(Of Integer)
        For i As Integer = 0 To m_Length - 1
            m_Positions.Add(i)
        Next
        m_CurrentIndex = m_Length - 1
    End Sub

    Private Function IsFree(ByVal position As Integer) As Boolean
        If position < 0 OrElse position >= m_List.Count Then
            Return False
        End If
        Return Not m_Positions.Contains(position)
    End Function

    ''//Add IDisposable support here


End Class

End Class

...你可以使用我的代码是这样的：

Dim list As New List(Of Integer)(...)
Dim iterator As New CombinationEnumerable(Of Integer)(list, 3)
    For Each combination In iterator
        Console.WriteLine(String.Join(", ", combination.Select(Function(el) el.ToString).ToArray))
    Next

我的代码给出了（在我的例子3）指定长度的组合，虽然，我才意识到，你希望有任何长度（我认为）的组合，但它是一个良好的开端。

Answer 3:

这不是很清楚，我在你希望你的VB代码返回它生成的组合什么样的形式，但为了简单起见，我们假设列表的列表。 VB确实允许递归和递归的解决方案是最简单的。 这样做的组合，而不是排列可以容易地获得，通过简单地尊重输入列表的排序。

所以，K个出列表L这N项长期的组合是：

1. 无，如果K>Ñ
2. 整个列表L，如果满足K ==ñ
3. 如果满足K <N，则两束的联合：那些包含L的第一项和任何K-1中的其它N-1项的组合; 加，其它N-1项K的组合。

在伪代码（例如使用.size给一个列表的长度，[]为空列表，.append将项目添加到列表，。头以获取列表的第一项，.tail拿到“列表中的所有，但L的第一”项目）：

function combinations(K, L):
  if K > L.size: return []
  else if K == L.size: 
    result = []
    result.append L
    return result
  else:
    result = []
    for each sublist in combinations(K-1, L.tail):
      subresult = []
      subresult.append L.head
      for each item in sublist:
        subresult.append item
      result.append subresult
    for each sublist in combinations(K, L.tail):
      result.append sublist
    return result

如果你承担更多的灵活列表操作语法本伪代码可以更加简洁。 例如，在Python（“可执行的伪代码”）用“切片”和“列表理解”的语法：

def combinations(K, L):
  if K > len(L): return []
  elif K == len(L): return [L]
  else: return [L[:1] + s for s in combinations(K-1, L[1:])
               ] + combinations(K, L[1:])

无论您是需要反复.append以冗长构造列表，或可以通过简洁列表理解符号构建他们来说，是一个语法细节（如头部的选择和尾VS列表切片表示法来获取列表的第一项VS休息）：伪代码是为了表达完全相同的想法（这也是英国在一个编号列表表达了同样的想法）。 您可以实现，它能够递归的任何语言的想法（当然，有些最小的列表操作 - ！）。

Answer 4:

我一扭，提供一个排序列表，首先由长 - 然后通过阿尔法

Imports System.Collections.Generic

Public Class LettersList

    Public Function GetList(ByVal aString As String) As List(Of String)
        Dim returnList As New List(Of String)

        ' Start the recursive method
        GetListofLetters(aString, returnList)

        ' Sort the list, first by length, second by alpha
        returnList.Sort(New ListSorter)

        Return returnList
    End Function

    Private Sub GetListofLetters(ByVal aString As String, ByVal aList As List(Of String))
        ' Alphabetize the word, to make letter key
        Dim tempString As String = Alphabetize(aString)

        ' If the key isn't blank and the list doesn't already have the key, add it
        If Not (String.IsNullOrEmpty(tempString)) AndAlso Not (aList.Contains(tempString)) Then
            aList.Add(tempString)
        End If

        ' Tear off a letter then recursify it
        For i As Integer = 0 To tempString.Length - 1
            GetListofLetters(tempString.Remove(i, 1), aList)
        Next
    End Sub

    Private Function Alphabetize(ByVal aString As String) As String
        ' Turn into a CharArray and then sort it
        Dim aCharArray As Char() = aString.ToCharArray()
        Array.Sort(aCharArray)
        Return New String(aCharArray)
    End Function

End Class

Public Class ListSorter
    Implements IComparer(Of String)

    Public Function Compare(ByVal x As String, ByVal y As String) As Integer Implements System.Collections.Generic.IComparer(Of String).Compare
        If x.Length = y.Length Then
            Return String.Compare(x, y)
        Else
            Return (x.Length - y.Length)
        End If
    End Function
End Class

Answer 5:

我可以提供以下解决方案 - 还不是很完善，并不快，而且它假定输入是一组，因此不包含重复的项目。 我将在以后添加一些解释。

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
   static void Main()
   {
      Int32 n = 5;
      Int32 k = 3;

      Boolean[] falseTrue = new[] { false, true };

      Boolean[] pattern = Enumerable.Range(0, n).Select(i => i < k).ToArray();
      Int32[] items = Enumerable.Range(1, n).ToArray();

      do
      {
         Int32[] combination = items.Where((e, i) => pattern[i]).ToArray();

         String[] stringItems = combination.Select(e => e.ToString()).ToArray();
         Console.WriteLine(String.Join(" ", stringItems));

         var right = pattern.SkipWhile(f => !f).SkipWhile(f => f).Skip(1);
         var left = pattern.Take(n - right.Count() - 1).Reverse().Skip(1);

         pattern = left.Concat(falseTrue).Concat(right).ToArray();
      }
      while (pattern.Count(f => f) == k);

      Console.ReadLine();
   }
}

它产生确定如果一个元素属于当前组合开始布尔模式的序列k倍真（1）在最左侧，其余所有假（0）。

  n = 5  k = 3

  11100
  11010
  10110
  01110
  11001
  10101
  01101
  10011
  01011
  00100

如下产生下一个图案。 假设当前的模式是以下内容。

00011110000110.....

左扫描到右，跳过所有零（假）。

000|11110000110....

进一步上扫描一（真）的第一个块。

0001111|0000110....

将所有除了最右边一回最左边跳过的。

1110001|0000110...

最后移到最右边跳过一个单一的姿势要正确。

1110000|1000110...

文章来源: How to Generate Combinations of Elements of a List in .NET 4.0