How to generate powersets with a maximum size in C#?

Question

I am trying to generate all powersets from a given list within a limit of given maximum size. I've found some great answers for how to generate powersets in general and admire the solution using bitmaps found here All Possible Combinations of a list of Values or here Computing Powersets in C#.

Is there a way to generate sets with a maximum size of 'maxSize' numbers in one set? E.g. my input is {1, 2, 3, 4, 5, 6}, but I only want results with 3 or less items. Is it possible to do within the one command? I have found a solution where I iterate over all items of the result, but this is quite inefficient for large inputs with smaller maxSize.

score 0 · Accepted Answer · edited Jul 28 '22 at 21:04

0

It's easy with recursion:

static public IEnumerable<List<int>> FindAllCombos(List<int> list, int maxSize, int minIndex = 0)
{
    yield return new List<int>();
    if (maxSize > 0)
        for (int i = minIndex; i < list.Count; i++)
            foreach (var set in FindAllCombos(list, maxSize - 1, i + 1))
            {
                set.Add(list[i]);
                yield return set;
            }
}

Note that the elements of the output sets will here be in the reverse order.

edited Jul 28 '22 at 21:04

TylerH

20,799
66
75
101

answered Jul 27 '22 at 14:04

M Kloster

679
4
13

Thank you, this does exactly what I want! I don't care about the order of the elements within the set, so that's fine. The only thing I had to fix was to remove the first (empty) element of the list, which I simply did after the method terminated. – Elphie Aug 02 '22 at 12:02

How to generate powersets with a maximum size in C#?

1 Answers1