ここで回答した質問と似ていますが、同じではない質問があります。
n個の要素のリストから要素のk個の組み合わせをすべて生成する関数が欲しいのですが。私は順列ではなく組み合わせを探していることに注意してください。また、kを変化させるための解決策が必要です（つまり、ループをハードコーディングすることはノーノーです）。
a）エレガントで、b）VB10 /.Net4.0でコーディングできるソリューションを探しています。
これは、a）LINQを必要とするソリューションは問題ない、b）C＃の「yield」コマンドを使用するソリューションは問題ないことを意味します。
組み合わせの順序は重要ではなく（つまり、辞書式順序、グレイコード、何を持っているか）、2つが競合している場合は、パフォーマンスよりも優雅さが優先されます。
（ここでのOCamlおよびC＃ソリューションは、VB10でコーディングできれば、完璧です。）
組み合わせのリストをk要素の配列として生成する C# のコード:
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 ( source ) で利用できます。
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) の組み合わせを提供しますが、任意の長さの組み合わせが必要であることに気付きました (私は思います)が、それは良いスタートです。
ひねりを加えて、最初に長さで、次にアルファで並べ替えられたリストを提供します
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
VB コードが生成した組み合わせをどのような形式で返すかは明確ではありませんが、簡単にするために、リストのリストを想定してみましょう。VB では再帰が許可されており、再帰的なソリューションが最も簡単です。入力リストの順序を順守するだけで、順列ではなく組み合わせを簡単に取得できます。
したがって、N アイテムの長さのリスト L からの 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 によってリストを冗長に構築する必要があるか、リスト内包表記によって簡潔に構築できるかは、構文の詳細です (リストの最初の項目と残りの項目を取得するための頭と尾とリストのスライス表記の選択と同様に) ): 疑似コードは、まったく同じアイデアを表現することを目的としています (これは、前の番号付きリストで英語で表現されたものと同じアイデアでもあります)。このアイデアは、再帰が可能な任意の言語で実装できます (もちろん、いくつかの最小限のリスト操作も可能です!-)。
次の解決策を提供できます-まだ完全ではなく、高速ではなく、入力がセットであると想定しているため、重複するアイテムは含まれていません。後で説明を少し加えます。
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....
1 の最初のブロックをさらにスキャンします (true)。
0001111|0000110....
一番右のもの以外のすべてのスキップされたものを一番左に戻します。
1110001|0000110...
最後に、一番右のスキップされたものを 1 つ右に移動します。
1110000|1000110...