すべてのサブセットを生成していた場合、長さnのリストに対して 2 n 個のサブセットを生成することになります。これを行う一般的な方法は、0 から 2 n -1 までのすべての数値iを反復処理し、 iに設定されているビットを使用して、 i番目のサブセットに含まれる項目を判別することです。これが機能するのは、任意のアイテムが特定のサブセットに存在するか存在しないかのいずれかであるため、nビットのすべての組み合わせを反復することにより、2 n 個のサブセットを反復することになります。
たとえば、(1, 2, 3) のサブセットを生成するには、0 から 7 までの数値を反復処理します。
0 = 000b → ()
1 = 001b → (1) 2
= 010b → ( 2 )
3 = 011b → (1, 2)
4 = 100b → (3)
5 = 101b → (1, 3 ) )
6 = 110 b → (2, 3)
7 = 111 b → (1, 2, 3)
問題では、各サブセットとその補数を生成して、相互に排他的なサブセットのペアを取得できます。これを行うと各ペアが繰り返されるため、最大 2 n -1 - 1 まで反復してから停止するだけで済みます。
1 = 001 b → (1) + (2, 3)
2 = 010 b → (2) + (1, 3)
3 = 011 b → (1, 2) + (3)
重複するアイテムを処理するには、リスト アイテムのサブセットではなく、リスト インデックスのサブセットを生成できます。リスト (1, 2, 2, 3) と同様に、代わりにリスト (0, 1, 2, 3) のサブセットを生成し、それらの数値を (1, 2, 2, 3) リストのインデックスとして使用します。基本的に、間接的なレベルを追加します。
これをすべてまとめた Python コードを次に示します。
#!/usr/bin/env python
def split_subsets(items):
subsets = set()
for n in xrange(1, 2 ** len(items) / 2):
# Use ith index if ith bit of n is set.
l_indices = [i for i in xrange(0, len(items)) if n & (1 << i) != 0]
# Use the indices NOT present in l_indices.
r_indices = [i for i in xrange(0, len(items)) if i not in l_indices]
# Get the items corresponding to the indices above.
l = tuple(items[i] for i in l_indices)
r = tuple(items[i] for i in r_indices)
# Swap l and r if they are reversed.
if (len(l), l) > (len(r), r):
l, r = r, l
subsets.add((l, r))
# Sort the subset pairs so the left items are in ascending order.
return sorted(subsets, key = lambda (l, r): (len(l), l))
for l, r in split_subsets([1, 2, 2, 3]):
print l, r
出力：
(1,) (2, 2, 3)
(2,) (1, 2, 3)
(3,) (1, 2, 2)
(1, 2) (2, 3)
(1, 3) (2, 2)