如何按照索引的二进制值中 1 的数量顺序遍历列表？ （Python最好）
How do I iterate over a list in order of the amounts of 1's in the binary value of the index? (Python preferably)
如果我有一个巨大的列表（比如 2^50 个元素），我该如何遍历这个列表，但是按照索引的二进制值中 1 的数量顺序，以最快的方式 Python?
例如，首先是 11111111，然后是 11111110、11111101、11111011、11110111、11101111、11011111、10111111、01111111，然后是 11111100 等
我需要这个的原因是因为我正在做动态规划来为给定集合 V 的每个子集找到一个值，用 value(subset) 表示并且因为有太多可能的子集我决定表示子集在二进制中，因此子集 {v1,v2,v5} 例如是 000010011。我必须按上述顺序迭代，因为我必须使用的递归函数具有基本情况值（V）= 0，即值（1111111111111）= 0，并进一步构建子集的大小减小，即 1 的数量二进制值。
如果有完全不同的完全不使用二进制的方法，请告诉我！非常感谢您阅读本文，
约斯特
编辑： 这是递归函数：
，其中 N(v) 是顶点 v 的邻居。（这是一个图问题）。
伪代码看起来像这样，对于集合 V 和子集 X:
value(V)=0
Forloop in described order:
pick a vertex v from V that is not in X and denote it in binary
subset, so that for example v = 001000000, where X = 010111101
#Use bitwise operator '|' to get intersections of binary values:
value(X) = value(X|v) + value(X|N(v)) + 1
PS：您可以在 python 中使用普通整数，按位运算符仍然有效：8|4 将 return 12：100|010 = 110
下面提出了两种不同的方法。
方法 1：基于组合的生成器
实现这一点的一种方法是在 on-bits 的数量上使用外循环，在 on-bits 的位置上使用内循环。对于内部循环，可以使用 combination generator 来遍历 on-bits 的位置。相应的序列将从所有 on-bits 的数字开始，然后是除了一个 on-bit 之外的所有数字，然后是除了两个 on-bits 之外的所有数字，...，最后以0（无 on-bits）。通过对 on-bits.
的位置求和 2^position，可以将 on-bit 位置的组合转换为数字
对于问题的用例，序列的元素将用作遍历相关列表的索引。
旋转门组合生成器在每次访问时迭代要在组合中换入和换出的小项目集。这种算法可能用于减少上述方法的计算要求，方法是根据哪些位将打开和哪些位将关闭来修改每次迭代的当前数字。
这是 Python 中的一个实现，它不使用旋转门方法，基于 Python 的 built-in itertools.combinations。函数下方的示例用法总共使用八位。对于生成序列中的每个数字，输出显示 1) 十进制表示，2) 二进制表示，以及 3) on-bits.
的计数
from itertools import combinations
def generator(num_bits):
powers = [2 ** exponent for exponent in range(num_bits - 1, -1, -1)]
for num_on in range(num_bits, -1, -1):
for positions in combinations(range(num_bits), num_on):
yield sum(powers[position] for position in positions)
for x in generator(8):
binary = f'{x:#010b}'
bit_count = binary.count('1')
print(f'{x:03} {binary} {bit_count}')
输出：
255 0b11111111 8
254 0b11111110 7
253 0b11111101 7
251 0b11111011 7
247 0b11110111 7
239 0b11101111 7
223 0b11011111 7
191 0b10111111 7
127 0b01111111 7
252 0b11111100 6
250 0b11111010 6
249 0b11111001 6
...
006 0b00000110 2
005 0b00000101 2
003 0b00000011 2
128 0b10000000 1
064 0b01000000 1
032 0b00100000 1
016 0b00010000 1
008 0b00001000 1
004 0b00000100 1
002 0b00000010 1
001 0b00000001 1
000 0b00000000 0
方法 2：有序索引列表
另一种方法——比之前的方法使用更多的内存——是计算每个数字中on-bits的数量（这里的“数字”是一个索引），然后创建一个数字列表他们的数量降序 on-bits.
这是 Python 中的一个实现。对于从 a 到 z 的字母，输出显示按其索引中的位数排序的字符，以及每个字符的索引、其二进制表示和 on-bits 的计数. bin(.).count('1')用于统计每个数字中on-its的个数。 Issue 29882 on bugs.python.org 建议 built-in bit_count 方法将在 Python 3.10 中可用。
letters = [
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
]
n = len(letters)
bit_counts = [bin(x).count('1') for x in range(n)]
indices_lookup = [[] for _ in range(len(bin(n)) - 2)]
for idx, bit_count in enumerate(bit_counts):
indices_lookup[bit_count].append(idx)
ordered_indices = []
for idxs in reversed(indices_lookup):
ordered_indices.extend(idxs)
for x in ordered_indices:
print(f'{letters[x]} {x:02} {x:#07b}')
输出：
p 15 0b01111 4
x 23 0b10111 4
h 07 0b00111 3
l 11 0b01011 3
n 13 0b01101 3
o 14 0b01110 3
t 19 0b10011 3
v 21 0b10101 3
w 22 0b10110 3
z 25 0b11001 3
d 03 0b00011 2
f 05 0b00101 2
g 06 0b00110 2
j 09 0b01001 2
k 10 0b01010 2
m 12 0b01100 2
r 17 0b10001 2
s 18 0b10010 2
u 20 0b10100 2
y 24 0b11000 2
b 01 0b00001 1
c 02 0b00010 1
e 04 0b00100 1
i 08 0b01000 1
q 16 0b10000 1
a 00 0b00000 0
如果我有一个巨大的列表（比如 2^50 个元素），我该如何遍历这个列表，但是按照索引的二进制值中 1 的数量顺序，以最快的方式 Python?
例如，首先是 11111111，然后是 11111110、11111101、11111011、11110111、11101111、11011111、10111111、01111111，然后是 11111100 等
我需要这个的原因是因为我正在做动态规划来为给定集合 V 的每个子集找到一个值，用 value(subset) 表示并且因为有太多可能的子集我决定表示子集在二进制中，因此子集 {v1,v2,v5} 例如是 000010011。我必须按上述顺序迭代，因为我必须使用的递归函数具有基本情况值（V）= 0，即值（1111111111111）= 0，并进一步构建子集的大小减小，即 1 的数量二进制值。
如果有完全不同的完全不使用二进制的方法，请告诉我！非常感谢您阅读本文， 约斯特
编辑： 这是递归函数：
value(V)=0
Forloop in described order:
pick a vertex v from V that is not in X and denote it in binary
subset, so that for example v = 001000000, where X = 010111101
#Use bitwise operator '|' to get intersections of binary values:
value(X) = value(X|v) + value(X|N(v)) + 1
PS：您可以在 python 中使用普通整数，按位运算符仍然有效：8|4 将 return 12：100|010 = 110
下面提出了两种不同的方法。
方法 1：基于组合的生成器
实现这一点的一种方法是在 on-bits 的数量上使用外循环，在 on-bits 的位置上使用内循环。对于内部循环，可以使用 combination generator 来遍历 on-bits 的位置。相应的序列将从所有 on-bits 的数字开始，然后是除了一个 on-bit 之外的所有数字，然后是除了两个 on-bits 之外的所有数字，...，最后以0（无 on-bits）。通过对 on-bits.
的位置求和2^position，可以将 on-bit 位置的组合转换为数字
对于问题的用例，序列的元素将用作遍历相关列表的索引。
旋转门组合生成器在每次访问时迭代要在组合中换入和换出的小项目集。这种算法可能用于减少上述方法的计算要求，方法是根据哪些位将打开和哪些位将关闭来修改每次迭代的当前数字。
这是 Python 中的一个实现，它不使用旋转门方法，基于 Python 的 built-in itertools.combinations。函数下方的示例用法总共使用八位。对于生成序列中的每个数字，输出显示 1) 十进制表示，2) 二进制表示，以及 3) on-bits.
from itertools import combinations
def generator(num_bits):
powers = [2 ** exponent for exponent in range(num_bits - 1, -1, -1)]
for num_on in range(num_bits, -1, -1):
for positions in combinations(range(num_bits), num_on):
yield sum(powers[position] for position in positions)
for x in generator(8):
binary = f'{x:#010b}'
bit_count = binary.count('1')
print(f'{x:03} {binary} {bit_count}')
输出：
255 0b11111111 8
254 0b11111110 7
253 0b11111101 7
251 0b11111011 7
247 0b11110111 7
239 0b11101111 7
223 0b11011111 7
191 0b10111111 7
127 0b01111111 7
252 0b11111100 6
250 0b11111010 6
249 0b11111001 6
...
006 0b00000110 2
005 0b00000101 2
003 0b00000011 2
128 0b10000000 1
064 0b01000000 1
032 0b00100000 1
016 0b00010000 1
008 0b00001000 1
004 0b00000100 1
002 0b00000010 1
001 0b00000001 1
000 0b00000000 0
方法 2：有序索引列表
另一种方法——比之前的方法使用更多的内存——是计算每个数字中on-bits的数量（这里的“数字”是一个索引），然后创建一个数字列表他们的数量降序 on-bits.
这是 Python 中的一个实现。对于从 a 到 z 的字母，输出显示按其索引中的位数排序的字符，以及每个字符的索引、其二进制表示和 on-bits 的计数. bin(.).count('1')用于统计每个数字中on-its的个数。 Issue 29882 on bugs.python.org 建议 built-in bit_count 方法将在 Python 3.10 中可用。
letters = [
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
]
n = len(letters)
bit_counts = [bin(x).count('1') for x in range(n)]
indices_lookup = [[] for _ in range(len(bin(n)) - 2)]
for idx, bit_count in enumerate(bit_counts):
indices_lookup[bit_count].append(idx)
ordered_indices = []
for idxs in reversed(indices_lookup):
ordered_indices.extend(idxs)
for x in ordered_indices:
print(f'{letters[x]} {x:02} {x:#07b}')
输出：
p 15 0b01111 4
x 23 0b10111 4
h 07 0b00111 3
l 11 0b01011 3
n 13 0b01101 3
o 14 0b01110 3
t 19 0b10011 3
v 21 0b10101 3
w 22 0b10110 3
z 25 0b11001 3
d 03 0b00011 2
f 05 0b00101 2
g 06 0b00110 2
j 09 0b01001 2
k 10 0b01010 2
m 12 0b01100 2
r 17 0b10001 2
s 18 0b10010 2
u 20 0b10100 2
y 24 0b11000 2
b 01 0b00001 1
c 02 0b00010 1
e 04 0b00100 1
i 08 0b01000 1
q 16 0b10000 1
a 00 0b00000 0