How to generate all possible combinations of 0-1 matrix in Python?
<p>How can generate all possible combinations of a 0-1 matrix of size K by N?</p>

<p>For example, if I take K=2 and N=2, I get the following combinations.</p>

<pre><code>combination 1
[0, 0;
 0, 0]; 
combination 2
[1, 0;
 0, 0]; 
combination 3
[0, 1;
 0, 0]; 
combination 4
[0, 0;
 1, 0]; 
combination 5
[0, 0;
 0, 1]; 
combination 6
[1, 1;
 0, 0]; 
combination 7
[1, 0;
 1, 0]; 
combination 8
[1, 0;
 0, 1]; 
combination 9
[0, 1;
 1, 0]; 
combination 10
[0, 1;
 0, 1]; 
combination 11
[0, 0;
 1, 1]; 
combination 12
[1, 1;
 1, 0]; 
combination 13
[0, 1;
 1, 1]; 
combination 14
[1, 0;
 1, 1]; 
combination 15
[1, 1;
 0, 1]; 
combination 16
[1, 1;
 1, 1]; 
</code></pre>

<p>An alternative approach to using <code>itertools.product</code> that is faster:</p>

<pre><code>def using_shifts(K, N):
    shifter = numpy.arange(K*N).reshape( (K, N) )
    return [(x &gt;&gt; shifter) % 2 for x in range(2 ** (K*N))]
</code></pre>

<p>How does this work?  We are exploiting that each desired array of <code>0</code> and <code>1</code> will correspond to the binary expansion of an integer.  For an integer <code>x</code> to find bit at index <code>y</code> we need to compute <code>(x &gt;&gt; y) % 2</code>.  </p>

<p>So here we can use <code>numpy</code> operations to find an array of indexes using the corresponding array operations.</p>

<p>Compared to <code>itertools.product</code>, relative timing is:</p>

<ul>
<li><code>using_shifts(2, 5)</code>: 1.9ms</li>
<li><code>using_itertools(2, 5)</code>: 2.8ms</li>
</ul>

python combinations