如何找到恰好有六个 1 和其余 0 的所有 32 位二进制数
How do I find all 32 bit binary numbers that have exactly six 1 and rest 0
我可以用蛮力做到这一点，但我希望有巧妙的编码，或者可能是现有的功能，或者我没有意识到的东西...
所以我想要一些数字示例：
00000000001111110000
11111100000000000000
01010101010100000000
10101010101000000000
00100100100100100100
完整排列。除了只有六个 1 的结果。不多。不低于。 64 或 32 位将是理想的。 16 位，如果提供答案。
我想你在这里需要的是使用 itertools 模块。
错误的解决方案
但是你需要小心，例如，使用 permutations 之类的东西只适用于非常小的输入。即：
像下面这样的东西会给你一个二进制表示：
>>> ["".join(v) for v in set(itertools.permutations(["1"]*2+["0"]*3))]
['11000', '01001', '00101', '00011', '10010', '01100', '01010', '10001', '00110', '10100']
然后获取这些数字的十进制表示：
>>> [int("".join(v), 16) for v in set(itertools.permutations(["1"]*2+["0"]*3))]
[69632, 4097, 257, 17, 65552, 4352, 4112, 65537, 272, 65792]
如果你想要包含 6 个 1 和 26 个 0 的 32 位，你可以使用：
>>> [int("".join(v), 16) for v in set(itertools.permutations(["1"]*6+["0"]*26))]
但是这个计算需要超级计算机来处理 (32!= 263130836933693530167218012160000000 )
体面的解决方案
所以一个更聪明的方法是使用 combinations，也许是这样的：
import itertools
num_bits = 32
num_ones = 6
lst = [
f"{sum([2**vv for vv in v]):b}".zfill(num_bits)
for v in list(itertools.combinations(range(num_bits), num_ones))
]
print(len(lst))
这会告诉我们在 32 位数字的整个范围内有 906192 个数字，其中有 6 个一。
学分：
此答案归功于@Mark Dickinson，他指出使用 permutations 是不可行的，并建议使用 combinations
好吧，我不是 Python 编码员，所以我无法 post 为您提供有效代码。相反，我可以做一个 C++ 一个...
如果您查看您的问题，您设置了 6 位和许多零...所以我将通过 6 个嵌套的 for 循环来计算所有可能的 1s 位置并设置这些位...
类似于：
for (i0= 0;i0<32-5;i0++)
for (i1=i0+1;i1<32-4;i1++)
for (i2=i1+1;i2<32-3;i2++)
for (i3=i2+1;i3<32-2;i3++)
for (i4=i3+1;i4<32-1;i4++)
for (i5=i4+1;i5<32-0;i5++)
// here i0,...,i5 marks the set bits positions
所以 O(2^32) 变得小于 `~O(26.25.24.23.22.21/16) 并且你不能比它更快，因为那意味着你会错过有效的解决方案...
我假设您想打印数字，因此为了加快速度，您可以从一开始就将数字计算为二进制数字字符串，以避免字符串和数字之间的转换缓慢...
嵌套的for循环可以编码为数组的增量操作（类似于bignum算法）
当我把所有东西放在一起时，我得到了这个 C++ 代码：
int generate()
{
const int n1=6; // number of set bits
const int n=32; // number of bits
char x[n+2]; // output number string
int i[n1],j,cnt; // nested for loops iterator variables and found solutions count
for (j=0;j<n;j++) x[j]='0'; x[j]='b'; j++; x[j]=0; // x = 0
for (j=0;j<n1;j++){ i[j]=j; x[i[j]]='1'; } // first solution
for (cnt=0;;)
{
// Form1->mm_log->Lines->Add(x); // here x is the valid answer to print
cnt++;
for (j=n1-1;j>=0;j--) // this emulates n1 nested for loops
{
x[i[j]]='0'; i[j]++;
if (i[j]<n-n1+j+1){ x[i[j]]='1'; break; }
}
if (j<0) break;
for (j++;j<n1;j++){ i[j]=i[j-1]+1; x[i[j]]='1'; }
}
return cnt; // found valid answers
};
当我将它与 n1=6,n=32 一起使用时，我得到了这个输出（不打印数字）：
cnt = 906192
它在 4.246 ms 上完成，在 AMD A8-5500 3.2GHz（win7 x64 32 位应用程序无线程）上，这对我来说已经足够快了...
请注意，一旦您开始在某处输出数字，速度将急剧下降。特别是如果你输出到控制台或任何东西......以某种方式缓冲输出可能会更好，比如一次输出 1024 个字符串数字等......但正如我之前提到的，我不是 Python 编码员所以它可能是已经被环境处理了...
最重要的是，一旦您将使用变量 n1,n，您可以对零而不是零执行相同的操作，并使用更快的方法（如果零较少，则使用嵌套的 for 循环来标记零而不是那些）
如果想要的解决方案编号是数字（而不是字符串），则可以重写它，因此 i[] 或 i0,..i5 保留位掩码而不是位位置...而不是inc/dec 你只需移动 left/right ... 不再需要 x 数组，因为数字将是 x = i0|...|i5 ...
您正在处理 multisets. There are many ways to achieve this and as @BPL points out, doing this efficiently is non-trivial. There are many great methods mentioned here: permutations with unique values 的排列。最干净的（不确定它是否最有效）是使用 sympy 模块中的 multiset_permutations。
import time
from sympy.utilities.iterables import multiset_permutations
t = time.process_time()
## Credit to @BPL for the general setup
multiPerms = ["".join(v) for v in multiset_permutations(["1"]*6+["0"]*26)]
elapsed_time = time.process_time() - t
print(elapsed_time)
在我的机器上，以上计算仅需 8 秒多一点。它也产生了将近一百万个结果：
len(multiPerms)
906192
您可以为数字中 1 的位置创建一个计数器数组，并 assemble 通过移动各自位置的位来创建它。我在下面创建了一个示例。它运行得非常快（在我的笔记本电脑上 32 位不到一秒）：
bitCount = 32
oneCount = 6
maxBit = 1<<(bitCount-1)
ones = [1<<b for b in reversed(range(oneCount)) ] # start with bits on low end
ones[0] >>= 1 # shift back 1st one because it will be incremented at start of loop
index = 0
result = []
while index < len(ones):
ones[index] <<= 1 # shift one at current position
if index == 0:
number = sum(ones) # build output number
result.append(number)
if ones[index] == maxBit:
index += 1 # go to next position when bit reaches max
elif index > 0:
index -= 1 # return to previous position
ones[index] = ones[index+1] # and prepare it to move up (relative to next)
64 位大约需要一分钟，大致与输出值的数量成正比。 O(n)
可以在递归生成器函数中更简洁地表达相同的方法，这将允许更有效地使用位模式：
def genOneBits(bitcount=32,onecount=6):
for bitPos in range(onecount-1,bitcount):
value = 1<<bitPos
if onecount == 1: yield value; continue
for otherBits in genOneBits(bitPos,onecount-1):
yield value + otherBits
result = [ n for n in genOneBits(32,6) ]
当您获得所有数字时，这并不更快，但它允许部分访问列表而无需遍历所有值。
如果您需要直接访问第 N 个位模式（例如，获取一个随机的一位模式），您可以使用以下函数。它的工作方式类似于索引列表，但无需生成模式列表。
def numOneBits(bitcount=32,onecount=6):
def factorial(X): return 1 if X < 2 else X * factorial(X-1)
return factorial(bitcount)//factorial(onecount)//factorial(bitcount-onecount)
def nthOneBits(N,bitcount=32,onecount=6):
if onecount == 1: return 1<<N
bitPos = 0
while bitPos<=bitcount-onecount:
group = numOneBits(bitcount-bitPos-1,onecount-1)
if N < group: break
N -= group
bitPos += 1
if bitPos>bitcount-onecount: return None
result = 1<<bitPos
result |= nthOneBits(N,bitcount-bitPos-1,onecount-1)<<(bitPos+1)
return result
# bit pattern at position 1000:
nthOneBit(1000) # --> 10485799 (00000000101000000000000000100111)
这使您能够获得不可能完全生成的非常大的整数的位模式：
nthOneBits(10000, bitcount=256, onecount=9)
# 77371252457588066994880639
# 100000000000000000000000000000000001000000000000000000000000000000000000000000001111111
值得注意的是，花样顺序并不遵循对应数字的数字顺序
虽然nthOneBits()可以立即生成任何图案，但在批量生成图案时，它比其他函数慢得多。如果您需要按顺序操作它们，您应该使用生成器函数而不是在 nthOneBits() 上循环。
此外，调整生成器使其以特定模式启动应该相当容易，这样您就可以充分利用这两种方法。
最后，在给定已知模式的情况下获得下一个位模式可能很有用。这是以下函数的作用：
def nextOneBits(N=0,bitcount=32,onecount=6):
if N == 0: return (1<<onecount)-1
bitPositions = []
for pos in range(bitcount):
bit = N%2
N //= 2
if bit==1: bitPositions.insert(0,pos)
index = 0
result = None
while index < onecount:
bitPositions[index] += 1
if bitPositions[index] == bitcount:
index += 1
continue
if index == 0:
result = sum( 1<<bp for bp in bitPositions )
break
if index > 0:
index -= 1
bitPositions[index] = bitPositions[index+1]
return result
nthOneBits(12) #--> 131103 00000000000000100000000000011111
nextOneBits(131103) #--> 262175 00000000000001000000000000011111 5.7ns
nthOneBits(13) #--> 262175 00000000000001000000000000011111 49.2ns
与 nthOneBits() 一样，这个不需要任何设置时间。它可以与 nthOneBits() 结合使用，以在给定位置获得初始模式后获得后续模式。 nextOneBits() 比 nthOneBits(i+1) 快得多，但仍然比生成器函数慢。
对于非常大的整数，使用 nthOneBits() 和 nextOneBits() 可能是唯一可行的选择。
我可以用蛮力做到这一点，但我希望有巧妙的编码，或者可能是现有的功能，或者我没有意识到的东西...
所以我想要一些数字示例：
00000000001111110000
11111100000000000000
01010101010100000000
10101010101000000000
00100100100100100100
完整排列。除了只有六个 1 的结果。不多。不低于。 64 或 32 位将是理想的。 16 位，如果提供答案。
我想你在这里需要的是使用 itertools 模块。
错误的解决方案
但是你需要小心，例如，使用 permutations 之类的东西只适用于非常小的输入。即：
像下面这样的东西会给你一个二进制表示：
>>> ["".join(v) for v in set(itertools.permutations(["1"]*2+["0"]*3))]
['11000', '01001', '00101', '00011', '10010', '01100', '01010', '10001', '00110', '10100']
然后获取这些数字的十进制表示：
>>> [int("".join(v), 16) for v in set(itertools.permutations(["1"]*2+["0"]*3))]
[69632, 4097, 257, 17, 65552, 4352, 4112, 65537, 272, 65792]
如果你想要包含 6 个 1 和 26 个 0 的 32 位，你可以使用：
>>> [int("".join(v), 16) for v in set(itertools.permutations(["1"]*6+["0"]*26))]
但是这个计算需要超级计算机来处理 (32!= 263130836933693530167218012160000000 )
体面的解决方案
所以一个更聪明的方法是使用 combinations，也许是这样的：
import itertools
num_bits = 32
num_ones = 6
lst = [
f"{sum([2**vv for vv in v]):b}".zfill(num_bits)
for v in list(itertools.combinations(range(num_bits), num_ones))
]
print(len(lst))
这会告诉我们在 32 位数字的整个范围内有 906192 个数字，其中有 6 个一。
学分：
此答案归功于@Mark Dickinson，他指出使用 permutations 是不可行的，并建议使用 combinations
好吧，我不是 Python 编码员，所以我无法 post 为您提供有效代码。相反，我可以做一个 C++ 一个...
如果您查看您的问题，您设置了 6 位和许多零...所以我将通过 6 个嵌套的 for 循环来计算所有可能的 1s 位置并设置这些位...
类似于：
for (i0= 0;i0<32-5;i0++)
for (i1=i0+1;i1<32-4;i1++)
for (i2=i1+1;i2<32-3;i2++)
for (i3=i2+1;i3<32-2;i3++)
for (i4=i3+1;i4<32-1;i4++)
for (i5=i4+1;i5<32-0;i5++)
// here i0,...,i5 marks the set bits positions
所以 O(2^32) 变得小于 `~O(26.25.24.23.22.21/16) 并且你不能比它更快，因为那意味着你会错过有效的解决方案...
我假设您想打印数字，因此为了加快速度，您可以从一开始就将数字计算为二进制数字字符串，以避免字符串和数字之间的转换缓慢...
嵌套的for循环可以编码为数组的增量操作（类似于bignum算法）
当我把所有东西放在一起时，我得到了这个 C++ 代码：
int generate()
{
const int n1=6; // number of set bits
const int n=32; // number of bits
char x[n+2]; // output number string
int i[n1],j,cnt; // nested for loops iterator variables and found solutions count
for (j=0;j<n;j++) x[j]='0'; x[j]='b'; j++; x[j]=0; // x = 0
for (j=0;j<n1;j++){ i[j]=j; x[i[j]]='1'; } // first solution
for (cnt=0;;)
{
// Form1->mm_log->Lines->Add(x); // here x is the valid answer to print
cnt++;
for (j=n1-1;j>=0;j--) // this emulates n1 nested for loops
{
x[i[j]]='0'; i[j]++;
if (i[j]<n-n1+j+1){ x[i[j]]='1'; break; }
}
if (j<0) break;
for (j++;j<n1;j++){ i[j]=i[j-1]+1; x[i[j]]='1'; }
}
return cnt; // found valid answers
};
当我将它与 n1=6,n=32 一起使用时，我得到了这个输出（不打印数字）：
cnt = 906192
它在 4.246 ms 上完成，在 AMD A8-5500 3.2GHz（win7 x64 32 位应用程序无线程）上，这对我来说已经足够快了...
请注意，一旦您开始在某处输出数字，速度将急剧下降。特别是如果你输出到控制台或任何东西......以某种方式缓冲输出可能会更好，比如一次输出 1024 个字符串数字等......但正如我之前提到的，我不是 Python 编码员所以它可能是已经被环境处理了...
最重要的是，一旦您将使用变量 n1,n，您可以对零而不是零执行相同的操作，并使用更快的方法（如果零较少，则使用嵌套的 for 循环来标记零而不是那些）
如果想要的解决方案编号是数字（而不是字符串），则可以重写它，因此 i[] 或 i0,..i5 保留位掩码而不是位位置...而不是inc/dec 你只需移动 left/right ... 不再需要 x 数组，因为数字将是 x = i0|...|i5 ...
您正在处理 multisets. There are many ways to achieve this and as @BPL points out, doing this efficiently is non-trivial. There are many great methods mentioned here: permutations with unique values 的排列。最干净的（不确定它是否最有效）是使用 sympy 模块中的 multiset_permutations。
import time
from sympy.utilities.iterables import multiset_permutations
t = time.process_time()
## Credit to @BPL for the general setup
multiPerms = ["".join(v) for v in multiset_permutations(["1"]*6+["0"]*26)]
elapsed_time = time.process_time() - t
print(elapsed_time)
在我的机器上，以上计算仅需 8 秒多一点。它也产生了将近一百万个结果：
len(multiPerms)
906192
您可以为数字中 1 的位置创建一个计数器数组，并 assemble 通过移动各自位置的位来创建它。我在下面创建了一个示例。它运行得非常快（在我的笔记本电脑上 32 位不到一秒）：
bitCount = 32
oneCount = 6
maxBit = 1<<(bitCount-1)
ones = [1<<b for b in reversed(range(oneCount)) ] # start with bits on low end
ones[0] >>= 1 # shift back 1st one because it will be incremented at start of loop
index = 0
result = []
while index < len(ones):
ones[index] <<= 1 # shift one at current position
if index == 0:
number = sum(ones) # build output number
result.append(number)
if ones[index] == maxBit:
index += 1 # go to next position when bit reaches max
elif index > 0:
index -= 1 # return to previous position
ones[index] = ones[index+1] # and prepare it to move up (relative to next)
64 位大约需要一分钟，大致与输出值的数量成正比。 O(n)
可以在递归生成器函数中更简洁地表达相同的方法，这将允许更有效地使用位模式：
def genOneBits(bitcount=32,onecount=6):
for bitPos in range(onecount-1,bitcount):
value = 1<<bitPos
if onecount == 1: yield value; continue
for otherBits in genOneBits(bitPos,onecount-1):
yield value + otherBits
result = [ n for n in genOneBits(32,6) ]
当您获得所有数字时，这并不更快，但它允许部分访问列表而无需遍历所有值。
如果您需要直接访问第 N 个位模式（例如，获取一个随机的一位模式），您可以使用以下函数。它的工作方式类似于索引列表，但无需生成模式列表。
def numOneBits(bitcount=32,onecount=6):
def factorial(X): return 1 if X < 2 else X * factorial(X-1)
return factorial(bitcount)//factorial(onecount)//factorial(bitcount-onecount)
def nthOneBits(N,bitcount=32,onecount=6):
if onecount == 1: return 1<<N
bitPos = 0
while bitPos<=bitcount-onecount:
group = numOneBits(bitcount-bitPos-1,onecount-1)
if N < group: break
N -= group
bitPos += 1
if bitPos>bitcount-onecount: return None
result = 1<<bitPos
result |= nthOneBits(N,bitcount-bitPos-1,onecount-1)<<(bitPos+1)
return result
# bit pattern at position 1000:
nthOneBit(1000) # --> 10485799 (00000000101000000000000000100111)
这使您能够获得不可能完全生成的非常大的整数的位模式：
nthOneBits(10000, bitcount=256, onecount=9)
# 77371252457588066994880639
# 100000000000000000000000000000000001000000000000000000000000000000000000000000001111111
值得注意的是，花样顺序并不遵循对应数字的数字顺序
虽然nthOneBits()可以立即生成任何图案，但在批量生成图案时，它比其他函数慢得多。如果您需要按顺序操作它们，您应该使用生成器函数而不是在 nthOneBits() 上循环。
此外，调整生成器使其以特定模式启动应该相当容易，这样您就可以充分利用这两种方法。
最后，在给定已知模式的情况下获得下一个位模式可能很有用。这是以下函数的作用：
def nextOneBits(N=0,bitcount=32,onecount=6):
if N == 0: return (1<<onecount)-1
bitPositions = []
for pos in range(bitcount):
bit = N%2
N //= 2
if bit==1: bitPositions.insert(0,pos)
index = 0
result = None
while index < onecount:
bitPositions[index] += 1
if bitPositions[index] == bitcount:
index += 1
continue
if index == 0:
result = sum( 1<<bp for bp in bitPositions )
break
if index > 0:
index -= 1
bitPositions[index] = bitPositions[index+1]
return result
nthOneBits(12) #--> 131103 00000000000000100000000000011111
nextOneBits(131103) #--> 262175 00000000000001000000000000011111 5.7ns
nthOneBits(13) #--> 262175 00000000000001000000000000011111 49.2ns
与 nthOneBits() 一样，这个不需要任何设置时间。它可以与 nthOneBits() 结合使用，以在给定位置获得初始模式后获得后续模式。 nextOneBits() 比 nthOneBits(i+1) 快得多，但仍然比生成器函数慢。
对于非常大的整数，使用 nthOneBits() 和 nextOneBits() 可能是唯一可行的选择。