最小长度子集的高效幂集算法

Question

最小长度子集的高效幂集算法

3

我使用以下C#函数获取长度受限的幂集子集：

string[] PowerSet(int min_len, string set)
{
    IEnumerable<IEnumerable<string>> seed = 
                    new List<IEnumerable<string>>() { Enumerable.Empty<string>() };

    return set.Replace(" ", "")
              .Split(',')
              .Aggregate(seed, (a, b) => a.Concat(a.Select(x => x.Concat(new[] { b }))))
              .Where(subset => subset.Count() >= min_len)
              .Select(subset => string.Join(",", subset))
              .ToArray();
}

问题在于，即使最小长度也很大，当原始集合很大时，算法也必须非常努力地工作。

例如：

    PowerSet(27, "1,11,12,17,22,127,128,135,240,254,277,284,292,296,399,309,322,326,333,439,440,442,447,567,580,590,692,697");

这应该很简单，但对于上述函数而言太冗长了。我正在寻找一种简洁修改我的函数，能够高效地处理这些情况。

- o17t H1H' S'k

1

相关链接：https://dev59.com/6UXRa4cB1Zd3GeqPv-8H#349919 - Gert Arnold

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam S · Accepted Answer

快速查看您的方法，其中一个低效之处在于创建了每个可能的子集，而不管它是否有足够的成员来保证包含在有限的超级集合中。

考虑改用以下扩展方法。该方法可以根据其计数修剪掉一些不必要的子集，以避免过多的计算。

public static List<List<T>> PowerSet<T>(List<T> startingSet, int minSubsetSize)
{
    List<List<T>> subsetList = new List<List<T>>();

    //The set bits of each intermediate value represent unique 
    //combinations from the startingSet.
    //We can start checking for combinations at (1<<minSubsetSize)-1 since
    //values less than that will not yield large enough subsets.
    int iLimit = 1 << startingSet.Count;
    for (int i = (1 << minSubsetSize)-1; i < iLimit; i++)
    {
        //Get the number of 1's in this 'i'
        int setBitCount = NumberOfSetBits(i);

        //Only include this subset if it will have at least minSubsetSize members.
        if (setBitCount >= minSubsetSize)
        {
            List<T> subset = new List<T>(setBitCount);

            for (int j = 0; j < startingSet.Count; j++)
            {
                //If the j'th bit in i is set, 
                //then add the j'th element of the startingSet to this subset.
                if ((i & (1 << j)) != 0)
                {
                    subset.Add(startingSet[j]);
                }
            }
            subsetList.Add(subset);
        }
    }
    return subsetList;
}

每个递增的i中设置位数告诉你子集中有多少个成员。如果没有足够的设置位，那么创建由比特组合表示的子集的工作就没有意义。NumberOfSetBits可以以多种方式实现。请参见如何计算32位整数中设置位数？ , 了解各种方法、解释和参考文献。这里是从SO问题中摘取的一个示例。

public static int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

现在，虽然这个解决方案适用于您的示例，但如果您将最小子集大小降低得太低或继续增加startingSet的大小，可能会遇到长运行时间和内存问题。没有在您的问题中发布特定要求，因此我无法判断此解决方案是否适合您和/或对您的预期输入情况的范围安全。

如果您发现此解决方案仍然过慢，则可以拆分操作以进行并行计算，可能使用PLINQ功能。

最后，如果您想使用LINQ装饰扩展方法，它看起来像以下内容。但是，如书面所述，我认为在没有对其进行一些更改的情况下，您将看到较慢的性能。

public static IEnumerable<List<T>> PowerSet<T>(List<T> startingSet, int minSubsetSize)
{
    var startingSetIndexes = Enumerable.Range(0, startingSet.Count).ToList();

    var candidates = Enumerable.Range((1 << minSubsetSize)-1, 1 << startingSet.Count)
                               .Where(p => NumberOfSetBits(p) >= minSubsetSize)
                               .ToList();

    foreach (int p in candidates)
    {
        yield return startingSetIndexes.Where(setInd => (p & (1 << setInd)) != 0)
                                       .Select(setInd => startingSet[setInd])
                                       .ToList();
    }
}