1
\$\begingroup\$

I would like to generate n subsets from objects from a List. Each subset should have k elements. Each subset should be unique.

The output should be a List of Lists.

My (very very slow way) is to create ALL possible subsets:

public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source)
{
    if (!source.Any())
        return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

    var element = source.Take(1);

    var haveNots = SubSetsOf(source.Skip(1));
    var haves = haveNots.Select(set => element.Concat(set));

    return haves.Concat(haveNots);
}

Afterwards I select the subsets with length k with the help of linq .where(x => x.Count() == k) and randomly select n of them.

This is very slow, because if the input list has 50 elements, there are 1125899906842624 different possible subsets. This is a big overhead.

How can I solve this problem more efficiently?

\$\endgroup\$
4
  • \$\begingroup\$ Not using recursion is one thing you can try. Google for something like "iterative backtracking". \$\endgroup\$
    – B.M.
    Commented Nov 9, 2017 at 14:29
  • \$\begingroup\$ Generate only the subsets with lenght K. \$\endgroup\$
    – Dido
    Commented Nov 9, 2017 at 14:30
  • \$\begingroup\$ Eric Lippert has written some blog posts about this type of problem you might find useful ericlippert.com/2014/10/13/producing-combinations-part-one \$\endgroup\$
    – juharr
    Commented Nov 9, 2017 at 17:43
  • \$\begingroup\$ Don't generate a list of lists. Generate an enumerable of enumerables -- which is what you are doing. Lists have to be generated all at once; enumerables can be generated a little at a time, which is often more efficient. \$\endgroup\$ Commented Nov 9, 2017 at 19:14

2 Answers 2

6
\$\begingroup\$

As noted in a comment, I did a series on my blog about interesting ways to solve this problem. But let's think about simple ways we can modify your program to solve your problem. We wish to produce all the subsets of source of size k, so let's add k to your method signature:

public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source, int k)
{

All right, what is our base case? Your original base case was "if the source is the empty set, then its only subset is the empty set". We must modify that, because our new contract is that we only return subsets of size k.

Let's be efficient. If k is zero then we can just take the early out; we know ahead of time that there is a subset of size zero regardless of the contents of source:

    if (k == 0)
        return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

Now we know that k is not zero. If the source is empty, or k is negative, then there must be no solution:

    if (k < 0 || !source.Any())
        return Enumerable.Empty<IEnumerable<T>>();

All right. That's our base case.

Now we must modify your recursive case. We now know that k is positive, and source is not empty.

There are two possibilities: either the first element is in the subset, or it is not. What are the subsets of size k that lack the first element?

    var haveNots = SubSetsOf(source.Skip(1), k);

Super. What are the subsets of size k that contain the first element? They are the subsets of size k-1 appended with that element.

    var element = source.Take(1);
    var smallerHaveNots = SubSetsOf(source.Skip(1), k-1);
    var haves = smallerHaveNots.Select(set => element.Concat(set));

And now we're done:

    return haves.Concat(haveNots);
}

A very small modification to your algorithm greatly speeds it up. But we could make it more efficient still. What if, instead of an IEnumerable<T> for source we had an ImmutableStack<T> for source? The only operations that we ever perform on source are:

  • Is it empty?
  • Extract the head
  • Recurse on the tail

which is exactly the operations of an immutable stack. We could do this entire operation but allocation far fewer helper objects; each time you call Skip(1), that generates a new object, but there's no need to do that; you could just use the tail of the stack.

Similarly: the outputs are a sequence of possibly-empty tails that sometimes have a head pushed onto them; you can get efficiency wins by making the outputs also immutable stacks.

See if you can go from there and make a really efficient implementation of this algorithm.

\$\endgroup\$
0
\$\begingroup\$

What you want is to generate all the nCr combinations of a set.

One approach is to use an integer to count from 1 to 2^N where N is the number of combinations. Then, if the number of set bits in each value is equal to the number of items in each combination that you want, output that combination.

Some sample code to demonstrate. Note that because this uses a uint to count, the maximum number of elements in each combination is 32.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp3
{
    class Program
    {
        static void Main()
        {
            string test = "ABCDEFG";

            foreach (var comb in SubSetsOf(test, 4))
                Console.WriteLine(string.Concat(comb));
        }

        public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> items, int k)
        {
            var list = items.ToList();
            return Combinations(list.Count, k).Select(comb => comb.Select(index => list[index]));
        }

        public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IList<T> items, int k)
        {
            return Combinations(items.Count, k).Select(comb => comb.Select(index => items[index]));
        }

        public static IEnumerable<IEnumerable<int>> Combinations(int n, int k)
        {
            long m = 1 << n;

            for (long i = 1; i < m; ++i)
                if (NumberOfSetBits((uint)i) == k)
                    yield return bitIndices((uint)i);
        }

        static IEnumerable<int> bitIndices(uint n)
        {
            uint mask = 1;

            for (int bit = 0; bit < 32; ++bit, mask <<= 1)
                if ((n & mask) != 0)
                    yield return bit;
        }

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

The output from this sample program is all the combinations of 4 characters taken from "ABCDEFG":

ABCD
ABCE
ABDE
ACDE
BCDE
ABCF
ABDF
ACDF
BCDF
ABEF
ACEF
BCEF
ADEF
BDEF
CDEF
ABCG
ABDG
ACDG
BCDG
ABEG
ACEG
BCEG
ADEG
BDEG
CDEG
ABFG
ACFG
BCFG
ADFG
BDFG
CDFG
AEFG
BEFG
CEFG
DEFG

There are 35 combinations. This is the correct number given that:

7C4 = 7!/((7-4)!x4!) = 7!/(3!x4!) = 35

I think this approach should be significantly faster than your current one, but time it to be sure!

Note that this works similarly to yours, in that it considers all possible subsets, but the difference is that it only counts the bits in an integer to determine if the subset should be emitted, and only then outputs the subset - which is what should make it a lot faster.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.