サイズ1の次元の立方体のすべての頂点を反復処理したいと思います。次のようnに実行できることはわかってitertools.productいます。
>>> n = 3
>>> for j in it.product((0,1), repeat=n) :
... print j
...
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
1ただし、座標で見つかったsの数に応じて、各頂点を異なる方法で処理する必要があります。 つまり(0, 1, 1)、すべての頂点が2つあるため、すべて同じ処理を受けます。上記のイテレータを使用してsの数を数えるのではなく、sの数で並べ替えられたデカルト積を生成したいと思います。(1, 0, 1)(1, 1, 0)111
>>> for ones in xrange(n) :
... for seq in magic_expression(ones, n) :
... print ones, seq
...
0 (0, 0, 0)
1 (0, 0, 1)
1 (0, 1, 0)
1 (1, 0, 0)
2 (0, 1, 1)
2 (1, 0, 1)
2 (1, 1, 0)
3 (1, 1, 1)
私の高校の数学の先生は、これらを一度に2つの要素の順列のように呼んでいたでしょう。最初の要素は何度も繰り返され、2番目の要素nはn - onesonesそれらが存在することを簡単に示すことがn! / ones! / (n - ones)!できます。
ウィキペディアによると、次のような辞書式順序でそれらを生成できます。
def lexicographical(ones, n) :
perm = [0] * (n - ones) + [1] * ones
yield tuple(perm)
while True :
k = None
for j in xrange(n - 1) :
if perm[j] < perm[j + 1] :
k = j
if k is None :
break
l = k + 1
for j in xrange(k + 2, n) :
if perm[k] < perm[j] :
l = j
perm[k], perm[l] = perm[l], perm[k]
perm[k+1:] = perm[-1:k:-1]
yield tuple(perm)
しかし、タイミングを合わせると、これは、の完全なデカルト積を数えることに対してのみ利益をもたらし始めn >= 10、次にones < 2、一般的な使用例ではない場合にのみ効果を発揮します。おそらくいくつかの強力なitertoolsブードゥーを使用して、またはまったく別のアルゴリズムを使用して、上記のコードを高速化するエレガントな方法はありますか？それが何か違いを生むのであれば、私は生成された順列の順序についてあまり気にすることはできませんでした。それとも私は数えることに自分自身を辞任する必要がありますか？
編集
私は提案された解決策についていくつかのタイミングを取りました。頂点を順番に消費すると、頂点がitertools.product生成され、カウントが常に最速になります。しかし、それらを1の数順に生成するには、リストを並べ替えるEeveeのソリューションが最速でn <= 6あり、それ以降、Camのソリューションは2つのうちで最速になります。
私はCamの解決策を受け入れました。なぜなら、それは求められていたものによりよく答えたものだからです。しかし、私が自分のコードに実装しようとしていることに関しては、私は自分自身を数えることに辞任するつもりです。