如何获得子集的所有可能组合？

Question

考虑一下这个List<string>

List<string> data = new List<string>();
data.Add("Text1");
data.Add("Text2");
data.Add("Text3");
data.Add("Text4");

我遇到的问题是:我如何才能获得列表子集的每个组合？有点像这样：

#Subset Dimension 4
Text1;Text2;Text3;Text4

#Subset Dimension 3
Text1;Text2;Text3;
Text1;Text2;Text4;
Text1;Text3;Text4;
Text2;Text3;Text4;

#Subset Dimension 2
Text1;Text2;
Text1;Text3;
Text1;Text4;
Text2;Text3;
Text2;Text4;

#Subset Dimension 1
Text1;
Text2;
Text3;
Text4;

我想出了一个不错的解决方案，值得在这里分享。

Answer 1

我认为，这个问题的答案需要一些性能测试。我会试一试。这是社区维基，请随时更新。

void PerfTest()
{
    var list = Enumerable.Range(0, 21).ToList();

    var t1 = GetDurationInMs(list.SubSets_LB);
    var t2 = GetDurationInMs(list.SubSets_Jodrell2);
    var t3 = GetDurationInMs(() => list.CalcCombinations(20));

    Console.WriteLine("{0}\n{1}\n{2}", t1, t2, t3);
}

long GetDurationInMs(Func<IEnumerable<IEnumerable<int>>> fxn)
{
    fxn(); //JIT???
    var count = 0;

    var sw = Stopwatch.StartNew();
    foreach (var ss in fxn())
    {
        count = ss.Sum();
    }
    return sw.ElapsedMilliseconds;
}

输出：

1281
1604 (_Jodrell not _Jodrell2)
6817

Jodrell更新

我已经构建了发布模式，也就是优化。当我通过Visual Studio运行时，我得不到1或2之间的一致偏差，但在重复运行LB的答案后，我得到的答案接近如下所示：

1190
1260
more

但是，如果我从命令行运行测试工具，而不是通过Visual Studio，我会得到如下所示的结果

987
879
still more

Answer 2

与Abaco的答案类似的逻辑，不同的实现……

foreach (var ss in data.SubSets_LB())
{
    Console.WriteLine(String.Join("; ",ss));
}

public static class SO_EXTENSIONS
{
    public static IEnumerable<IEnumerable<T>> SubSets_LB<T>(
      this IEnumerable<T> enumerable)
    {
        List<T> list = enumerable.ToList();
        ulong upper = (ulong)1 << list.Count;

        for (ulong i = 0; i < upper; i++)
        {
            List<T> l = new List<T>(list.Count);
            for (int j = 0; j < sizeof(ulong) * 8; j++)
            {
                if (((ulong)1 << j) >= upper) break;

                if (((i >> j) & 1) == 1)
                {
                    l.Add(list[j]);
                }
            }

            yield return l;
        }
    }
}

Answer 3

编辑

我已经接受了性能挑战，下面是我的合并，它接受了所有答案中最好的。在我的测试中，它似乎拥有最好的性能。

public static IEnumerable<IEnumerable<T>> SubSets_Jodrell2<T>(
    this IEnumerable<T> source)
{
    var list = source.ToList();
    var limit = (ulong)(1 << list.Count);

    for (var i = limit; i > 0; i--)
    {
        yield return list.SubSet(i);
    }
}

private static IEnumerable<T> SubSet<T>(
    this IList<T> source, ulong bits)
{
    for (var i = 0; i < source.Count; i++)
    {
        if (((bits >> i) & 1) == 1)
        {
            yield return source[i];
        }
    }
}

同样的想法，几乎和L.B's answer一样，但我有自己的解释。

我避免使用内部List和Math.Pow。

public static IEnumerable<IEnumerable<T>> SubSets_Jodrell(
    this IEnumerable<T> source)
{
    var count = source.Count();

    if (count > 64)
    {
        throw new OverflowException("Not Supported ...");
    }

    var limit = (ulong)(1 << count) - 2;

    for (var i = limit; i > 0; i--)
    {
        yield return source.SubSet(i);
    }
}

private static IEnumerable<T> SubSet<T>(
    this IEnumerable<T> source,
    ulong bits)
{
    var check = (ulong)1;
    foreach (var t in source)
    {
        if ((bits & check) > 0)
        {
            yield return t;
        }

        check <<= 1;
    }
}

您将注意到，这些方法不能处理初始集中超过64个元素，但无论如何，这都需要一段时间。