.NET में एक सूची <T> के तत्वों 4.0

Question

मैं एक सवाल है कि इसी तरह, लेकिन समान नहीं है, के लिए एक जवाब here.

मैं एक समारोह कश्मीर के सभी उत्पन्न चाहते हैं के संयोजन उत्पन्न करने के लिए कैसे एन तत्वों की सूची से तत्वों के संयोजन। ध्यान दें कि मैं संयोजनों की तलाश में हूं, क्रमपरिवर्तन नहीं, और हमें के (यानी, लूप को हार्ड-कोडिंग एक नो-नो) के लिए समाधान की आवश्यकता है।

मैं एक समाधान की तलाश में हूं जो एक है) सुरुचिपूर्ण, और बी) वीबी 10/नेट 4.0 में कोड किया जा सकता है।

इसका मतलब है ए) समाधान LINQ की आवश्यकता समाधान ठीक है, बी) सी # "उपज" कमांड का उपयोग करने वाले लोग नहीं हैं।

संयोजनों का क्रम महत्वपूर्ण नहीं है (यानी, लेक्सिकोोग्राफिकल, ग्रे-कोड, क्या है-आप) और लालित्य में प्रदर्शन होने पर लालित्य प्रदर्शन पर अनुकूल है।

(OCaml और सी # समाधान here, सही हो अगर वे VB10 में कोडित किया जा सकता है जाएगा।)

Answer 1

कोड कि कश्मीर तत्वों की सरणियों के रूप में संयोजन की सूची का उत्पादन:

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

संग्रह प्रारंभकर्ता वाक्य रचना यहां इस्तेमाल किया वीबी 2010 (source) में उपलब्ध है।

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

मैं निम्नलिखित समाधान प्रदान कर सकता हूं - अभी तक सही नहीं, तेज़ नहीं, और यह मानता है कि इनपुट एक सेट है, इसलिए इसमें कोई डुप्लिकेट आइटम नहीं है। मैं बाद में कुछ स्पष्टीकरण जोड़ने जा रहा हूँ।

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... 

Answer 4

यह किस रूप में आप अपने VB कोड के संयोजन उत्पन्न लौटना चाहते में मेरे लिए स्पष्ट नहीं है, लेकिन सादगी के लिए की सूची की एक सूची मान लें। वीबी रिकर्सन की अनुमति देता है, और एक पुनरावर्ती समाधान सबसे सरल है। इनपुट सूची के आदेश का सम्मान करके, क्रमपरिवर्तन के बजाय संयोजन करना आसानी से प्राप्त किया जा सकता है।

तो, एक सूची एल है कि एन आइटम से बाहर कश्मीर आइटम के संयोजन लंबे होते हैं:

1. कोई नहीं है, अगर कश्मीर> एन
2. पूरी सूची एल, अगर कश्मीर == एन
3. यदि के < एन, तो दो बंचों का संघ: जिनके पास एल की पहली वस्तु और अन्य एन -1 वस्तुओं के के -1 के संयोजन शामिल हैं; इसके अलावा, अन्य एन -1 वस्तुओं के के संयोजन के संयोजन।

स्यूडोकोड (उदाहरण के लिए का उपयोग करके सूची की दूरी देने के लिए .Size, [] एक खाली सूची के रूप में, .append एक सूची के लिए एक आइटम जोड़ने के लिए, एक सूची के पहले आइटम प्राप्त करने के लिए .head, .tail पाने के लिए "सभी लेकिन पहले" एल आइटम) की सूची:

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 

यह स्यूडोकोड अधिक संक्षिप्त यदि आप और अधिक लचीला सूची-हेरफेर वाक्य रचना मान बनाया जा सकता है। उदाहरण के लिए, पायथन ("निष्पादन योग्य स्यूडोकोड") में "टुकड़ा करने की क्रिया" और "सूची समझ" सिंटैक्स का उपयोग:

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

आप verbosely दोहराया .append द्वारा सूचियों का निर्माण करने की जरूरत है, या संक्षेप में उन्हें सूची समझ अंकन द्वारा निर्माण कर सकते हैं या नहीं , एक वाक्यविन्यास विस्तार है (जैसा सूची और सूची के पहले आइटम को प्राप्त करने के लिए सिर और पूंछ बनाम सूची स्लाइसिंग नोटेशन की पसंद है): स्यूडोकोड का उद्देश्य बिल्कुल वही विचार व्यक्त करना है (जो भी वही विचार व्यक्त किया गया है पिछली क्रमांकित सूची में अंग्रेजी)। आप इस विचार को किसी भी भाषा में कार्यान्वित कर सकते हैं जो रिकर्सन करने में सक्षम है (और, ज़ाहिर है, कुछ न्यूनतम सूची संचालन! -)। सी # में

Answer 5

मेरे मोड़, लंबाई द्वारा एक क्रमबद्ध सूची, दे रहे थे पहले - तो अल्फा द्वारा

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