9

我有一个与此处回答的问题相似但不相同的问题。

我想要一个函数从 n 个元素的列表中生成所有元素的k组合。请注意，我正在寻找组合，而不是排列，并且我们需要一个用于改变k的解决方案（即，对循环进行硬编码是不行的）。

我正在寻找一种解决方案，a) 优雅，b) 可以在 VB10/.Net 4.0 中编码。

这意味着 a) 需要 LINQ 的解决方案是可以的，b) 那些使用 C#“yield”命令的解决方案不是。

组合的顺序并不重要（即，字典顺序、格雷码、你有什么），如果两者发生冲突，优雅比性能更受青睐。

（这里的 OCaml 和 C# 解决方案将是完美的，如果它们可以在 VB10 中编码。）

4

5 回答 5

8

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 中可用（源代码）。

于 2009-07-20T00:13:01.193 回答
1

我尝试创建一个可以在 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），但我刚刚意识到您希望拥有任意长度的组合（我认为），但这是一个好的开始。

于 2009-07-13T20:41:48.100 回答
1

我不清楚您希望您的 VB 代码以何种形式返回它生成的组合，但为简单起见，让我们假设一个列表列表。VB 确实允许递归，递归解决方案是最简单的。通过简单地尊重输入列表的顺序，可以很容易地获得组合而不是排列。

因此，列表 L 中有 N 个项目长的 K 个项目的组合是：

  1. 无，如果 K > N
  2. 整个列表 L，如果 K == N
  3. 如果 K < N，则两个串的并集：包含 L 的第一项和其他 N-1 项的 K-1 的任意组合的那些；加上其他 N-1 个项目的 K 个组合。

在伪代码中（例如，使用 .size 给出列表的长度，[] 作为空列表，.append 将项目添加到列表中，.head 获取列表的第一项，.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 来详细地构造列表，还是可以通过列表理解符号简明地构造它们，都是语法细节（就像选择头尾与列表切片符号来获取列表的第一项与其余项一样） )：伪代码旨在表达完全相同的想法（这也是之前编号列表中用英文表达的相同想法）。您可以用任何能够递归的语言来实现这个想法（当然，还有一些最小的列表操作！-）。

于 2009-07-18T21:02:03.157 回答
1

我的转折，提供一个排序列表，首先按长度 - 然后按 alpha

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
于 2011-03-15T17:25:19.953 回答
0

我可以提供以下解决方案 - 还不完美，速度不快，并且它假设输入是一个集合，因此不包含重复项。稍后我将添加一些解释。

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最左边的时间 true (1) 开始，其余时间均为 false (0)。

  n = 5 k = 3

  11100
  11010
  10110
  01110
  11001
  10101
  01101
  10011
  01011
  00100

下一个模式生成如下。假设当前模式如下。

00011110000110.....

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

000|11110000110....

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

0001111|0000110....

将除最右侧之外的所有跳过的内容移回最左侧。

1110001|0000110...

最后将最右边跳过的一个位置向右移动。

1110000|1000110...
于 2009-07-14T17:33:51.420 回答