Как генерировать комбинации элементов списка <T> в.NET 4.0

Question

Как генерировать комбинации элементов списка <T> в.NET 4.0

Не забывайте, что замена не делает замены в строке, но возвращает новую строку с замененными символами. Следующее удалит разрывы строки (не, заменяют их). Я использовал бы @Brian R. Метод Bondy при замене их чем-то еще, возможно, обернутым как дополнительный метод. Не забудьте проверять на нулевые значения сначала перед тем, чтобы называть Замену или дополнительные предоставленные методы.

string line = ...

line = line.Replace( "\r", "").Replace( "\n", "" );

Как дополнительные методы:

public static class StringExtensions
{
   public static string RemoveLineBreaks( this string lines )
   {
      return lines.Replace( "\r", "").Replace( "\n", "" );
   }

   public static string ReplaceLineBreaks( this string lines, string replacement )
   {
      return lines.Replace( "\r\n", replacement )
                  .Replace( "\r", replacement )
                  .Replace( "\n", replacement );
   }
}

9

vb.net linq algorithm combinations

задан Community 23 May 2017 в 11:45

4 ответа

Я попытался создать перечислимый объект, который может выполнить эту задачу в 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 в моем примере), хотя я только что понял, что вы хотите иметь комбинации любых длина (я думаю), но это хорошее начало.

1

ответ дан 4 December 2019 в 21:11

I can offer the following solution - not yet perfect, not fast, and it assumes the input is a set, hence contains no duplicate items. I am going to add some explanation later.

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

It generates a sequence of boolean patterns that determine if an element belongs to the current combination starting with k times true (1) at the very left and the rest all false (0).

  n = 5  k = 3

  11100
  11010
  10110
  01110
  11001
  10101
  01101
  10011
  01011
  00100

The next pattern is generated as follows. Assume the current pattern is the following.

00011110000110.....

Scan from left to right and skip all zeros (false).

000|11110000110....

Scan further over the first block of ones (true).

0001111|0000110....

Move all the skipped ones besides the rightmost one back to the very left.

1110001|0000110...

And finally move the rightmost skipped one a single position to the right.

1110000|1000110...

0

ответ дан 4 December 2019 в 21:11

Мне не ясно, в какой форме вы хотите, чтобы ваш код VB возвращал генерируемые им комбинации, но для простоты предположим, что это список списков. VB допускает рекурсию, и рекурсивное решение является самым простым. Выполнение комбинаций, а не перестановок можно легко получить, просто соблюдая порядок во входном списке.

Итак, комбинации K элементов из списка L, длина которого составляет N элементов:

нет, если K> N
весь список L, если K == N
если K

В псевдокоде (используя, например, .size, чтобы указать длину списка, [] как пустой список, .append, чтобы добавить элемент в список, .head получить список ' s первый элемент, .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