从给定列表中的任何k元素中找到最大值(count(count(set bit)))

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

因此，如果我选择数字6（ 11 0）和1（00 1 ），则分别为2和1套件IE 。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)

我的问题是线：

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

AS k = 2 ，我手动i [0]和i [1]接受了此。但是如何动态。

我也在寻找答案而无需使用列表理解，因为我的列表大小可能会变化为2至10^18，这会导致内存超过。

如果您可以提出任何其他逻辑，那将非常有用。

Answer 1

我希望其中有一种。我真的认为不需要组合，因为只有设置最多的项目才能构成结果。考虑以下内容：

给定输入，以下我认为计算结果：

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]

这样：

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

这可以通过使用大小k的heapq并插入(bin(v)[2:].count('1'), v)，然后通过提取数字来将结果作为乘积。heapq功能nlargest可以很好地工作

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

请注意，l可以是迭代器。这在恒定空间中运行。内存使用量取决于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)])

可以工作