How to generator all combinations (memory efficient algorithm)?

Question

I need a way to generate all combinations (NOT permutations) of elements in a list in C# (non-repeating, order does not matter).

I have seen several solutions that propose using recursion, however they require building the entire list before returning (memory inefficient).

I was hoping there is a way to create a generator that could yield the current combination without storing all other combinations during its iteration. Does anyone know of any efficient solutions?

Welcome to Stack Overflow. This is not a code/SQL/regex writing service, where you post a list of your requirements and language of choice and a code monkey churns out code for you. We're more than happy to help, but we expect you to make an effort to solve the problem yourself first. Once you've done so, you can explain the problem you're having, include the **relevant** portions of your work, and ask a specific question, and we'll try to help. Good luck. — Ken White, Apr 07 '18 at 23:27
https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/iterators — Hans Passant, Apr 07 '18 at 23:28
https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer — Hans Passant, Apr 07 '18 at 23:29
I am looking for a solution that finds combinations, not permutations. — Krypt, Apr 08 '18 at 00:44
If you have so many items that allocating another array of them is a problem then you will never get all combinations 2^n is somewhat large number ;) — Alexei Levenkov, Apr 08 '18 at 07:16

score 0 · Answer 1 · answered Apr 09 '18 at 00:11

Just create an iterator method using yield return, like so:

   public class Combinations: IEnumerable<Combination> {
        public IEnumerator<T> GetEnumerator()
        {
            Combination currentCombination = Combination.FirstCombination(); 
            while (currentCombination.IsValid()) {
                yield return currentCombination;
                currentCombination = currentCombination.NextCombination(); // return invalid combo if currentCombination is the last possible combination
            }
        }
   }

Of course you still have to write the Combination class but that should be relatively straightforward. You should be able to generate the next combination from the current one. For example, say there are N elements in the list, you just have to increment a base-N number containing N digits and as you do that you will generate all combinations.

For the FirstCombination and NextCombination methods, you could use BitArray of length N, and implement a += 1 operator to step to the next combination. The bits in the array would represent the combination. — sjb-sjb, Jun 26 '22 at 14:53

score 0 · Answer 2 · answered Apr 09 '18 at 09:09

There are M = 2^n - 1 possible combinations (if we exclude empty combination). So just make for-loop in range 1..2^n-1 and map loop counter value to item combination - if k-th bit is set, use k-th item in combination. For example, 5=101binary corresponds to combination (item[0], item[2])

How to generator all combinations (memory efficient algorithm)?

2 Answers2