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

Question

У меня есть вопрос, который похож, но не идентичен тому, на который был дан ответ вот.

Я хотел бы, чтобы функция генерировала все k-комбинации элементов из списка из n элементов.Обратите внимание, что я ищу комбинации, а не перестановки, и что нам нужно решение для изменения k (т. е. жестко кодировать циклы запрещено).

Я ищу решение, которое является а) элегантным и б) может быть закодировано в VB10 / .Net 4.0.

Это означает, что а) решения, требующие LINQ, приемлемы, б) решения, использующие команду C # "yield", - нет.

Порядок комбинаций не важен (например, лексикографический, серый код, что у вас есть), и элегантность предпочтительнее производительности, если они противоречат друг другу.

(Решения 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 > N
2. весь список L, если K == N
3. если K < N, тогда объединение двух сгустков:те, которые содержат первый элемент из L и любую из комбинаций K-1 других N-1 элементов;плюс комбинации из K других N-1 предметов.

В псевдокоде (используя, например, .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:])

Нужно ли вам подробно создавать списки с помощью repeated .append или вы можете кратко создавать их с помощью нотации для понимания списка, зависит от синтаксических деталей (как и выбор заголовка и хвоста в сравнении с нотацией для нарезки списка, чтобы получить первый элемент списка по сравнению с остальными):псевдокод предназначен для выражения точно такой же идеи (которая также является той же идеей, выраженной на английском языке в предыдущем нумерованном списке).Вы можете реализовать эту идею на любом языке, который способен к рекурсии (и, конечно, к некоторым минимальным операциям со списком!-).

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 умножьте значение true (1) в самом левом, а все остальные значения false (0).

  n = 5  k = 3

  11100
  11010
  10110
  01110
  11001
  10101
  01101
  10011
  01011
  00100

Следующий шаблон генерируется следующим образом.Предположим, что текущая схема следующая.

00011110000110.....

Сканируйте слева направо и пропускайте все нули (false).

000|11110000110....

Выполните дальнейшее сканирование по первому блоку единиц (true).

0001111|0000110....

Переместите все пропущенные элементы, кроме самого правого, обратно в самый левый.

1110001|0000110...

И, наконец, переместите самый правый пропущенный элемент на одну позицию вправо.

1110000|1000110...