指定されたリストの任意のk要素のmax（sum（count（set bits）））を見つけるには

Question

与えられたリストからk要素のセットされたビットの合計の最大値を見つけるのに問題があります。

は考える：

n = 4 # length of list 
k = 2 # choose only k elements of list whose count(sum(set bits)) is max 
list l= 6 2 1 0 

を私はそれぞれ2および1セットビットで番号6（ 0）と1（00 ）を選択した場合ので、それらを追加することは私にセットされたビットの最大数を与えますすなわち、私が試したどのような3

です：私の問題はラインである

from itertools import combinations 
s = list(map(int,raw_input().split())) 
n = s[0] 
k = s[1] 

l = list(map(int,raw_input().split())) 

comb = list(combinations(l, k)) 
# print comb 
ad = [] 
for i in comb: 
    x = bin(i[0])[2:].count('1')+bin(i[1])[2:].count('1') 
    ad.append(x) 
# print ad 
print max(ad) 

：K = 2として

x = bin(i[0])[2:].count('1')+bin(i[1])[2:].count('1') 

、私はこれを手動で取ったI [0]とi [1]。 これを行う方法動的に。

また、私のリストサイズは2〜10^18まで変化する可能性があるので、リストの理解を使用しないで、の回答を探しています。

他のロジックを提案できる場合は、非常に便利です。

Answer 1

を働くことができると思います。私は本当に組み合わせが必要でないと思うのは、ほとんどのビットがセットされたアイテムだけが結果を補うことができるからです。考えてみましょう以下：heapqを使用して

>>> sorted(l, key=lambda v: bin(v)[2:].count('1'), reverse=True)[:2] 
[6, 2] 

これは、入力経由でストリーミングさせることができます。このような

n = 4 # length of list 
k = 2 # choose only k elements of list whose count(sum(set bits)) is max 
l = [6, 2, 1, 0] 

：

は

あなたの入力を考えると、私は思う次は結果を計算サイズがkであり、(bin(v)[2:].count('1'), v)を挿入すると、数値を抽出することによって結果が得られます。 heapq機能nlargestはlはイテレータことができることをうまく

>>> import heapq 
>>> heapq.nlargest(k, l, key=lambda v: bin(v)[2:].count('1')) 
[6, 2] 

注意を動作します。これは一定の空間で動作します。メモリ使用量はイテレータの長さに依存しないkに依存します。ロジック用

>>> sum(bin(v)[2:].count('1') for v in [6,2]) 
3 

Answer 2

私は

x = sum([bin(i[kk])[2:].count('1') for kk in range(k)]) 

が、私はそこでのソートがあることを期待