时间戳

首页 > 解决方案 > 用 k 1s 获得所有二进制组合的高效算法

algorithm - 用 k 1s 获得所有二进制组合的高效算法

问题描述

我有n位，我知道其中k位是 1。
我应该从n = 4 和k = 2 的算法中得到的结果是：

1100
1010
1001
0110
0101
0011

我已经尝试了一些递归策略，但它们都不足以满足我的需求（n可能 > 50000）。
我也看过类似问题的答案，但效率不够。

我认为通过利用 1 和 0 没有区别这一事实，我可以让某些东西快速运行，这样我就可以避免很多会产生相同结果的迭代。
同样，我注意到我可以避免计算多达一半的结果，因为它们中的大多数只是彼此相反的二进制（即 1100 -> 0011）。

标签： algorithmperformancebinary

解决方案

在 C++ 中，您可以使用std::next_permutation，但您应该找到 std::string 以外的其他内容作为您的类型。

#include <algorithm>
#include <string>
#include <iostream>
void Permute(int n = 8, int k = 3) {
    std::string s = std::string(n-k, '0')+std::string(k, '1');
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}

00000111
00001011
00001101
00001110
00010011
00010101
00010110
00011001
00011010
00011100
00100011
00100101
00100110
00101001
00101010
00101100
00110001
00110010
00110100
00111000
01000011
01000101
01000110
01001001
01001010
01001100
01010001
01010010
01010100
01011000
01100001
01100010
01100100
01101000
01110000
10000011
10000101
10000110
10001001
10001010
10001100
10010001
10010010
10010100
10011000
10100001
10100010
10100100
10101000
10110000
11000001
11000010
11000100
11001000
11010000
11100000

推荐阅读