0

对于以下字符a,b,c,d，我想找到以下组合。

序列总是排序的。我想知道我应该如何找到组合？

一种
b
C
d

抗体
交流
广告

公元前
BD

光盘

美国广播公司
abd
acd

bcd

A B C D
4

5 回答 5

4

你想要的是每一个组合。通常，在获取组合时，您会得到特定大小 n 的所有组合。我们将首先创建该方法以从序列中获取大小 n 的组合：

public static IEnumerable<IEnumerable<T>> Combinations<T>(
      this IEnumerable<T> source, int n)
{
    if (n == 0)
        yield return Enumerable.Empty<T>();


    int count = 1;
    foreach (T item in source)
    {
        foreach (var innerSequence in source.Skip(count).Combinations(n - 1))
        {
            yield return new T[] { item }.Concat(innerSequence);
        }
        count++;
    }
}

一旦你有了它，将所有 n 的 n 组合从 1 到序列的大小是一件简单的事情：

public static IEnumerable<IEnumerable<T>> AllCombinations<T>(this IList<T> source)
{
    IEnumerable<IEnumerable<T>> output = Enumerable.Empty<IEnumerable<T>>();
    for (int i = 0; i < source.Count; i++)
    {
        output = output.Concat(source.Combinations(i));
    }
    return output;
}

一些使用它的示例代码：

var list = new List<string> { "a", "b", "c", "d" };

foreach (var sequence in list.AllCombinations())
{
    Console.WriteLine(string.Join(" ", sequence));
}

值得注意的是，除了最小的输入序列之外，此操作对于所有其他操作都非常昂贵。这并不是最有效的，但即使你确实计算出最后一点性能，你也无法计算超过 15-20 的序列组合，这取决于你愿意等待多长时间并且你的电脑有多好。

于 2012-10-22T15:28:32.957 回答
0

您可以使用Combinatorics库为您计算它们（文档），但正如 Servy 所说，数据的长度是需要多长时间的主要因素。

于 2012-10-22T15:39:10.207 回答
0

它们不是真正的子集，因为没有什么可以阻止您的输入序列包含重复项，但以下扩展方法应该在一般情况下工作：

public static IEnumerable<IEnumerable<T>> Subsets<T>(this IEnumerable<T> source)
{
    List<T[]> yielded = new List<T[]> { new T[0] };
    foreach(T t in source)
    {
        List<T[]> newlyYielded = new List<T[]>();
        foreach(var y in yielded)
        {
            var newSubset = y.Concat(new[] {t}).ToArray();
            newlyYielded.Add(newSubset);
            yield return newSubset;
        }
        yielded.AddRange(newlyYielded);
    }
}

基本上从一个空序列开始，它添加了附加第一个项目的空序列。然后对于这两个序列中的每一个，它都会添加该序列并附加下一个项目。然后对于这四个序列中的每一个......

这必须保留每个生成的序列的副本，因此会占用大量内存。

要从字符串中取出字符串，您可以将其称为

"abcd".Subsets().Select(chars => new string(chars.ToArray()))

如果您不想有很多字符，您可以利用可以直接计算第 n 个子集的事实：

public static int SubsetCount(this string s)
{
    return 2 << s.Length;
}
public static string NthSubset(this string s, int n)
{
    var b = New StringBuilder();
    int i = 0;
    while (n > 0)
    {
        if ((n&1)==1) b.Append(s[i]);
        i++;
        n >>= 1;
    }
    return b.ToString();
}
于 2012-10-22T16:01:45.417 回答
0

我编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。我没有看过@Bobson 建议的 Cominatorics 库，但我相信我的课程可能更快、更高效。它执行以下任务：

  1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。

  2. 将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人，但我可能是错的。

  3. 将已排序二项式系数表中的索引转换为相应的 K 索引。我相信它可能比您找到的链接更快。

  4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

  5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可执行上述 4 种方法。提供了访问器方法来访问表。

  6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

您的问题的解决方案涉及为每个 N 选择 K 案例生成 K 索引。因此，在上面的示例中，N（A、B、C、D）有 4 种可能性，代码（在 C# 中）看起来像这样：

int TotalNumberOfValuesInSet = 4;
int N = TotalNumberOfValuesInSet;
// Loop thru all the possible groups of combinations.
for (int K = N - 1; K < N; K++)
{
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   int[] KIndexes = new int[K];
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination, which in this case
      // are the indexes to each letter in the set starting with index zero.
      BC.GetKIndexes(Loop, KIndexes);
      // Do whatever processing that needs to be done with the indicies in KIndexes.
      ...
   }
   // Handle the final combination which in this case is ABCD since since K < N.
   ...
}
于 2012-10-22T16:19:30.493 回答
0

上面servy的代码非常优雅，但它不会产生与源代码长度相同的组合。

for (int i = 0; i < source.Count; i++) should be
for (int i = 0; i <= source.Count; i++).

下面是 vb.net 变体，它不能使用 yield。

<Extension()>
Public Function Combinations(Of T)(source As IEnumerable(Of T), n As Integer) As IEnumerable(Of IEnumerable(Of T))
    Dim lstResults As New List(Of IEnumerable(Of T))

    If n = 0 Then
        lstResults.Add(Enumerable.Empty(Of T))
    Else
        Dim count As Integer = 1


        For Each item As T In source
            For Each innerSequence In source.Skip(count).Combinations(n - 1)
                lstResults.Add(New T() {item}.Concat(innerSequence))
            Next
            count += 1
        Next
    End If

    Return lstResults

End Function

<Extension()>
Public Function AllCombinations(Of T)(source As IList(Of T)) As IEnumerable(Of IEnumerable(Of T))
    Dim output As IEnumerable(Of IEnumerable(Of T)) = Enumerable.Empty(Of IEnumerable(Of T))()

    For i As Integer = 0 To source.Count
        output = output.Concat(source.Combinations(i))
    Next
    Return output

End Function
于 2013-11-27T08:18:17.007 回答