C# 组合迭代器

• 下载源代码 - 19.18 KB

引言

在我的上一篇文章《一个 C# 排列迭代器》中，我介绍了一种紧凑的方式来对序列进行排列。 在本文中，我将扩展我的迭代器以包含组合。

Using the Code

这个迭代器以递归方式工作。 递归终止条件是选择 0 个元素时，此时序列将按原样返回。 在递归情况下，它比排列迭代器复杂一些。 该算法通过保留第一个元素，并对序列的其余部分进行递归调用来工作。 这会迭代地进行 (n) 次，其中 (n) 是序列的长度。 但是，每次迭代都会以不断缩短的序列长度调用递归。 例如，以下是选择来自 5 个序列的 2 个元素的过程的描述（每次迭代的结果是前 2 个元素）

产生的序列	注释	结果（前 2 个元素）
12345	初始序列和第一个结果	12
13452	内部旋转（从第 2 个元素开始）	13
14523	内部旋转	14
15234	内部旋转	15
23451	外部旋转	23
24531	内部旋转 - 请注意，最后一个元素现在被排除在旋转之外	24
25341	内部旋转	25
34512	外部旋转	34
35412	内部旋转 - 请注意，最后两个元素现在被排除在旋转之外	35
45123	外部旋转	45

这是代码

private static void RotateLeft<T>(IList<T> sequence, int start, int count)
{
    T tmp = sequence[start];
    sequence.RemoveAt(start);
    sequence.Insert(start + count - 1, tmp);
}

public static IEnumerable<IList<T>> Combinations<T>(
    IList<T> sequence, 
    int start, 
    int count, 
    int choose)
{
    if (choose == 0) yield return sequence;
    else
    {
        for (int i = 0; i < count; i++)
        {
            foreach (var perm in Combinations(
                                        sequence,
                                        start + 1,
                                        count - 1 - i,
                                        choose - 1))
                yield return perm;
            RotateLeft(sequence, start, count);
        }
    }
}

请注意，每次迭代都会返回一个全长的序列，但是结果实际上包含在序列的前 (m) 个元素中，其中 (m) 是我们选择从序列中选择的元素数。

对 Combinations 函数的初始调用应将 0 作为 start 参数，并将序列长度作为 count 参数传递。 为了方便起见，我们可以重载该调用，如下所示

public static IEnumerable<IList<T>> Combinations<T>(
    IList<T> sequence, 
    int choose)
{
    return Combinations(sequence, 0, sequence.Count, choose);
}

以下是迭代 string "abcdef" 中 3 个字符组合的示例。 请注意，我正在使用 Take 扩展方法来仅获取迭代结果中的结果部分。

private static void CombinationsOverString(string s, int count)
{
    foreach (var comb in Iterator.Combinations(s.ToCharArray().ToList(), count))
    {
        string r = new string(comb.Take(count).ToArray());
        Console.Write("{0,-8}", r);
    }
    Console.WriteLine();
}

输出

abc     abd     abe     abf     acd     ace     acf     ade     adf     aef
bcd     bce     bcf     bde     bdf     bef     cde     cdf     cef     def

这是使用我上一篇文章中的排列迭代器对这些组合进行排列的示例。

private static void CombinationsPermutations(string s, int count)
{
    foreach (var combo in Iterator.Combinations(
        s.ToCharArray().ToList(), 
        count))
    {
        foreach (var permu in Iterator.Permutations(combo, count))
        {
            string r = new string(permu.Take(count).ToArray());
            Console.Write("{0,-8}", r);
        }
    }
    Console.WriteLine();
}

输出

abc     bac     cab     acb     bca     cba     abd     bad     dab     adb
bda     dba     abe     bae     eab     aeb     bea     eba     abf     baf
fab     afb     bfa     fba     acd     cad     dac     adc     cda     dca
ace     cae     eac     aec     cea     eca     acf     caf     fac     afc
cfa     fca     ade     dae     ead     aed     dea     eda     adf     daf
fad     afd     dfa     fda     aef     eaf     fae     afe     efa     fea
bcd     cbd     dbc     bdc     cdb     dcb     bce     cbe     ebc     bec
ceb     ecb     bcf     cbf     fbc     bfc     cfb     fcb     bde     dbe
ebd     bed     deb     edb     bdf     dbf     fbd     bfd     dfb     fdb
bef     ebf     fbe     bfe     efb     feb     cde     dce     ecd     ced
dec     edc     cdf     dcf     fcd     cfd     dfc     fdc     cef     ecf
fce     cfe     efc     fec     def     edf     fde     dfe     efd     fed

关注点

在互联网上可以找到许多组合和排列迭代器的实现，但我特别喜欢这个，因为它占用的内存很少，并且不会创建任何不必要的对象。 其推论是，迭代器运行时序列会被修改；如果不需要这样做，则应在原始序列的副本上运行迭代。

历史

• 2009 年 11 月 16 日 - 初始发布