эффективный алгоритм powerset для подмножеств минимальной длины

Question

Я использую следующую функцию 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");

должно быть очень простым, но слишком длинным для вышеуказанной функции. я ищу краткую модификацию моей функции, которая могла бы эффективно обработать эти случаи.

Answer 1

Беглый взгляд на ваш метод, одна из неэффективностей заключается в том, что создается каждое возможное подмножество, независимо от того, имеет ли оно достаточно членов, чтобы гарантировать включение в ограниченный супернабор.

Рассмотрите возможность реализации следующего расширения.метод вместоЭтот метод может обрезать некоторые ненужные подмножества на основе их количества, чтобы избежать лишних вычислений.

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();
    }
}