Prune a list of combinations based on sets
<p>While this question is formulated using the Python programming language, I believe it is more of a programming logic problem. </p>

<p>I have a list of all possible combinations, i.e.: n choose k</p>

<p>I can prepare such a list using</p>

<pre><code>import itertools
bits_list = list(itertools.combinations(range(n), k))
</code></pre>

<p>If 'n' is 100, and `k' is 5, then the length of 'bits_list' will be 75287520.</p>

<p>Now, I want to prune this list, such that numbers appear in groups, or they don't. Let's use the following sets as an example:</p>

<p>Set 1: [0, 1, 2] <br />
Set 2: [57, 58] <br />
Set 3: [10, 15, 20, 25] <br />
Set 4: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]</p>

<p>Here each set needs to appear in any member of the bits_list together, or not at all. </p>

<p>So far, I only have been able to think of a brute-force if-else method of solving this problem, but the number of if-else conditions will be very large this way. </p>

<p>Here's what I have:</p>

<pre><code>bits_list = [x for x in list(itertools.combinations(range(n), k)) 
             if all(y in x for y in [0, 1, 2]) or
             all(y not in x for y in [0, 1, 2])]
</code></pre>

<p>Now, this only covered Set 1. I would like to do this for many sets. If the length of the set is longer than the value of k, we can ignore the set (for example, k = 5 and Set 4).  </p>

<p>Note, that the ultimate aim is to have 'k' iterate over a range, say [5:25] and work on the appended list. The size of the list grows exponentially here and computationally speaking, very expensive!</p>

<p>With 'k' as 10, the python interpreter interrupts the process before completion on any average laptop with 16 GB RAM. I need to find a solution that fits in the memory of a relatively modern server (not a cluster or a server farm). </p>

<p>Any help is greatly appreciated! </p>

<p>P.S.: Intuitively, think of this problem as generating all the possible cases for people boarding a public bus or train system. Usually, you board an entire group or you don't board anyone.</p>

<p><hr />
UPDATE:</p>

<ol>
<li><p>For the given sets above, if k = 5, then a valid member of bits_list would be [0, 1, 2, 57, 58], i.e.: a combination of Set1 and Set2. If k = 10, then we could have built Set1 + Set2 + Set3 + NoSetElement as a possible member. @DonkeyKong's solution made me realize I haven't mentioned this explicitly in my question. </p></li>
<li><p>I have a lot of sets; I intend to use enough sets to prune the full list of combinations such that the bits_list eventually fits into memory. </p></li>
<li><p>@9000's suggestion is perfectly valid here, that during each iteration, I can save the combinations as actual bits. </p></li>
</ol>