Làm thế nào để Tạo kết hợp của yếu tố của một danh sách <T> trong .NET 4.0

Question

Tôi có một câu hỏi đó là tương tự, nhưng không giống nhau, một sự trả lời here.

Tôi muốn một chức năng tạo ra tất cả các k -bao gồm các phần tử từ một danh sách các phần tử n. Lưu ý rằng tôi đang tìm kiếm các kết hợp, không hoán vị và chúng tôi cần một giải pháp để thay đổi k (tức là, mã hóa cứng các vòng lặp là không có).

Tôi đang tìm một giải pháp là a) thanh lịch và b) có thể được mã hóa bằng VB10/.Net 4.0.

Điều này có nghĩa là a) các giải pháp yêu cầu LINQ là ok, b) những người sử dụng lệnh C# "yield" thì không.

Thứ tự của các kết hợp không quan trọng (tức là, từ điển lexicographical, Gray-code, những gì bạn có) và sự thanh lịch được ưu tiên hơn hiệu suất, nếu cả hai xung đột nhau.

(The OCaml và C# giải pháp here sẽ được hoàn hảo, nếu họ có thể được mã hóa trong VB10.)

Answer 1

Mã trong C# mà tạo ra danh sách các tổ hợp như mảng của k yếu tố:

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; 
    } 
} 

Collection initializer cú pháp sử dụng ở đây là có sẵn trong VB 2010 (source).

Answer 2

tôi đã cố gắng tạo ra một đếm được rằng có thể hoàn thành nhiệm vụ này trong VB. Đây là kết quả:

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 

... và bạn có thể sử dụng mã của tôi theo cách này:

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 

Mã của tôi cho sự kết hợp của một chiều dài quy định (3 trong ví dụ của tôi) tuy nhiên, tôi chỉ nhận ra rằng bạn muốn có sự kết hợp của bất kỳ chiều dài (tôi nghĩ), nhưng đó là một khởi đầu tốt.

Answer 3

Tôi có thể cung cấp giải pháp sau đây - chưa hoàn hảo, không nhanh và giả định đầu vào là bộ, do đó không chứa các mục trùng lặp. Tôi sẽ thêm một số lời giải thích sau.

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(); 
    } 
} 

Nó tạo ra một chuỗi các mô hình boolean xác định nếu một yếu tố thuộc về sự kết hợp giữa hiện tại bắt đầu với k lần đúng (1) tại rất trái và phần còn lại tất cả các sai lầm (0).

 
    n = 5 k = 3 

    11100 
    11010 
    10110 
    01110 
    11001 
    10101 
    01101 
    10011 
    01011 
    00100 

Mẫu tiếp theo được tạo như sau. Giả sử mẫu hiện tại là như sau.

00011110000110..... 

Quét từ trái sang phải và bỏ qua tất cả số không (sai).

000|11110000110.... 

Quét thêm khối thứ nhất (đúng).

0001111|0000110.... 

Di chuyển tất cả những người đã bỏ qua bên cạnh một bên phải từ bên trái sang bên trái.

1110001|0000110... 

Và cuối cùng di chuyển phần cuối cùng bên phải một vị trí duy nhất sang phải.

1110000|1000110... 

Answer 4

Không rõ ràng với tôi về hình thức bạn muốn mã VB trả lại kết hợp tạo ra, nhưng để đơn giản, hãy giả sử danh sách danh sách. VB cho phép đệ quy, và một giải pháp đệ quy đơn giản nhất. Làm kết hợp thay vì hoán vị có thể thu được dễ dàng, bằng cách đơn giản tôn trọng thứ tự của danh sách đầu vào.

Vì vậy, sự kết hợp các mặt hàng K ra khỏi một L danh sách đó là N mục dài là:

1. none, nếu K> N
2. the whole list L, nếu K == N
3. nếu K < N, thì sự kết hợp của hai chùm: những thứ chứa mục đầu tiên của L và bất kỳ kết hợp nào của K-1 của các mặt hàng N-1 khác; cộng với, sự kết hợp của K của các mặt hàng N-1 khác.

Trong mã giả (sử dụng ví dụ .size để cung cấp độ dài của danh sách, [] làm danh sách trống, hãy thêm mục vào danh sách, .head để nhận mục đầu tiên của danh sách, .tail để nhận danh sách các mục "tất cả trừ mục đầu tiên" của 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 

Mã giả này có thể súc tích hơn nếu bạn cho rằng cú pháp thao tác danh sách linh hoạt hơn. Ví dụ, trong Python ("giả thực thi") sử dụng "cắt" và "danh sách hiểu" cú pháp:

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:]) 

Cho dù bạn cần một cách chi tiết xây dựng danh mục do .append lặp đi lặp lại, hoặc ngắn gọn có thể xây dựng chúng bằng cách ký hiệu hiểu danh sách , là một chi tiết cú pháp (như là sự lựa chọn đầu và đuôi vs danh sách cắt ký hiệu để có được mục đầu tiên của danh sách so với phần còn lại): mã giả nhằm thể hiện chính xác cùng một ý tưởng (cũng là ý tưởng tương tự được thể hiện trong Tiếng Anh trong danh sách được đánh số trước đó). Bạn có thể thực hiện ý tưởng bằng bất kỳ ngôn ngữ nào có khả năng đệ quy (và, tất nhiên, một số hoạt động danh sách tối thiểu!).

Answer 5

xoắn của tôi, cung cấp một danh sách được sắp xếp, đầu tiên theo chiều dài - sau đó bởi 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