Most efficient way to generate "ordered subsets" of a sequence
<p>I need to generate all "ordered subsets" (apologies if I'm not using correct mathematical terminology) of a sequence in Python, with omitted elements replaced with <code>None</code>.Given <code>[1, 2]</code>, I want <code>[(1, 2), (1, None), (None, 2), (None, None)]</code>. Each "ordered subset" should have the property that at each position, it is either exactly the same element as in the seed sequence, or it is <code>None</code>.</p>

<p>I can fairly easily generate subsets with omitted elements missing with the following:</p>

<pre><code>from itertools import combinations
for length in xrange(len(items), 0, -1):
    for combination in combinations(items, length):
        yield combination
</code></pre>

<p>I can't figure out what the most effective way of reconstructing the missing elements, would be though. My first thought is to do something like this:</p>

<pre><code>from itertools import combinations
indexes = range(len(items))
for length in xrange(len(items), 0, -1):
    for combination in combinations(indexes, length):
        yield tuple(items[i] if i in combination else None for i in indexes)
</code></pre>

<p>Just wondering if anyone can spot any obvious deficiencies in this, or if there's a more efficient solution I've missed. (Note that the <code>items</code> will be a fairly short list, typically under 10 elements, so I am not concerned about the O(N) search of "combination" in the inner loop).</p>
