Python 3.xでビット並べ替えを生成する最速の方法

Question

可能なすべてのNを生成する必要があります.Kビットが設定されているK個のNビットの番号を選択します。私が思い付くことができた 最良かつ最も簡潔なオプションが非常に遅いです：

def kbits(n, k): 
    result = set() 
    for bits in itertools.combinations(range(n), k): 
     s = 0 
     for bit in bits: 
      s |= 1 << bit 
     result.add(s) 
    return result 

kbits(25, 12)私のマシン上で8.3sを取りました。

どうすれば速くすることができますか？たとえば、すべてのビットを一括して設定する方法がありますが、すべてをループすることはできません。

Answer 1

あなたのkbits(25, 12)は、それぞれを一度だけ計算する必要があるとき（そしてそれを実行したときに、小計結果を構築するのではなくsum()の組み込みを使用することができます）、同じ25の累乗を500万回以上計算します。あなたが実際にこの結果を達成するために何をしようとしている

def kbits(n, k): 
    powers = [1 << e for e in range(n)] 
    return {sum(bits) for bits in itertools.combinations(powers, k)}