logo标签列表

如何找到所有恰好有6个1和其余为0的32位二进制数？

pythonalgorithmmathbinarycombinatorics
5

我可以用蛮力方法完成这个任务，但是我希望有一些聪明的编码方式，或者已有的函数，或者我没有意识到的方法...

下面是我需要的一些数字示例：

00000000001111110000
11111100000000000000
01010101010100000000
10101010101000000000
00100100100100100100

完全排列。但结果必须仅包含六个 1。不多，不少。64 或 32 位最理想。如果这能够给出答案，则 16 位也可行。

4个回答
4
我认为你需要使用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个1。

致谢：

感谢 @Mark Dickinson 指出使用排列是不可行的，并建议使用组合。

1
这样做不行，至少在合理的时间内是不可能完成的。在你最后的例子中，itertools.permutations 调用将会遍历 32! = 263130836933693530167218012160000000 种排列方式。即使我们乐观地假设我们可以处理每纳秒一个排列，它仍然需要超过 8 百万亿年才能完成。 - Mark Dickinson
@Mark Dickinson 哦，你说得对！我认为这个问题非常简单，甚至没有考虑过性能方面的影响，感谢你指出来，我会编辑我的答案的 ;) - BPL
1
我认为 itertools.combinations 可以胜任。使用 itertools.combinations(range(32), 6)，并将返回的每个元组解释为给出1的位置。 - Mark Dickinson
@MarkDickinson 编辑了我的答案，在我的笔记本电脑上计算需要3.6秒...可能有比这更快的解决方案，但大约4秒比8万亿年好多了 :) - BPL
@BPL 是的，甚至有更快的方法，即使是像我回答中的朴素嵌套for循环（一个设置位）也要快得多...在我的设置上约为4ms，但大部分时间差异将在处理解决方案列表的内存分配方面...因为我不在任何地方存储结果... - Spektre
1

很抱歉，我不是Python编程人员，因此无法为您发布有效的代码。相反，我可以提供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 循环可以编码为数组的增量操作（类似于大数算术）。
当我把所有东西放在一起时，我得到了这个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

它在 AMD A8-5500 3.2GHz（win7 x64 32bit应用程序无线程）上以 4.246 毫秒 完成，对我来说足够快了...

请注意，一旦您开始在某个地方输出数字，速度将急剧下降。特别是如果您输出到控制台或其他地方...最好以某种方式缓冲输出，例如一次输出 1024 个字符串数字等等...但正如我之前提到的，我不是 Python 程序员，所以环境可能已经处理了这个问题...

除此之外，一旦您玩弄变量 n1，n，您可以使用零而不是一来进行相同的操作，并使用更快的方法（如果零比一少，则使用嵌套的 for 循环来标记零）

如果想要的解决方案数字是作为数字而不是字符串，则可以重写代码，使 i[] 或 i0，..i5 包含位掩码，而不是位位置...而不是增加/减少，您只需左/右移即可...不再需要 x 数组，因为数字将是 x = i0|...|i5 ...

1
你可以为数字中的1的位置创建一个计数器数组，并通过将它们在各自的位置上进行位移来组装它。我下面创建了一个示例。它运行得非常快（在我的笔记本电脑上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()可能是唯一实用的选项。
0

您正在处理多重集合的排列。有许多方法可以实现这一点，正如@BPL所指出的那样，高效地完成这项工作并不容易。这里提到了许多很好的方法：具有唯一值的排列。最干净的方法（不确定是否最有效）是使用 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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接