3

如何生成所有可能的 n 位字符串组合？我需要以最快的方式生成 20 位字符串的所有组合。（我目前的实现是通过按位与和右移操作完成的，但我正在寻找一种更快的技术）。

我需要将位字符串存储在数组（或列表）中以获取相应的十进制数，例如-

0 --> 0 0 0

1 --> 0 0 1

2 --> 0 1 0... ETC。

任何的想法？

4

6 回答 6

7

Python

>> n = 3
>> l = [bin(x)[2:].rjust(n, '0') for x in range(2**n)]
>> print l
['000', '001', '010', '011', '100', '101', '110', '111']
于 2012-09-08T08:00:33.727 回答
3

只需以二进制表示形式输出 0 到 2^n - 1 的数字，恰好 n 位。

于 2012-09-07T21:53:59.550 回答
3 
for (unsigned long i = 0; i < (1<<20); ++i) {
    // do something with it
}

Anunsigned long 是位序列。

如果您想要的是一串字符'0'and '1'，那么您i每次都可以转换为该格式。您可以利用连续数字通常共享一个长的初始子字符串这一事实来加快速度。所以你可以做这样的事情：

char bitstring[21];
for (unsigned int i = 0; i < (1<<10); ++i) {
    write_bitstring10(i, bitstring);
    for (unsigned int j = 0; j < (1<<10); ++j) {
        write_bitstring10(j, bitstring + 10);
        // do something with bitstring
    }
}

我只在那里从 1 个循环增加到 2 个循环，但我从位到字符的转换比以前多 50%。您可以尝试以下方法：

  • 使用更多循环
  • 不均匀地拆分循环，可能是 15-5 而不是 10-10
  • 编写一个函数，它接受一串 0 和 1，并在其上加 1。这很容易：找到最后一个'0'，将其更改为 a '1'，并将其后面的所有'1's 更改为'0'。

要极其优化write_bitstring，4 的倍数是好的，因为在大多数架构上，您可以一次在一个单词中写入 4 个字符：

开始：

assert(CHAR_BIT == 8);
uint32_t bitstring[21 / 4]; // not char array, we need to ensure alignment
((char*)bitstring)[20] = 0; // nul terminate

函数定义：

const uint32_t little_endian_lookup = {
    ('0' << 24) | ('0' << 16) | ('0' << 8) | ('0' << 0),
    ('1' << 24) | ('0' << 16) | ('0' << 8) | ('0' << 0),
    ('1' << 24) | ('1' << 16) | ('0' << 8) | ('0' << 0),
    // etc.
};
// might need big-endian version too

#define lookup little_endian_lookup // example of configuration

void write_bitstring20(unsigned long value, uint32_t *dst) {
    dst[0] = lookup[(value & 0xF0000) >> 16];
    dst[1] = lookup[(value & 0x0F000) >> 12];
    dst[2] = lookup[(value & 0x00F00) >> 8];
    dst[3] = lookup[(value & 0x000F0) >> 4];
    dst[4] = lookup[(value & 0x0000F)];
}

我还没有测试过这些：显然你有责任编写一个可以用来做实验的基准。

于 2012-09-07T21:54:28.723 回答
0 
for (i = 0; i < 1048576; i++) {
   printf('%d', i);
}

将 int 版本 i 转换为二进制字符串作为 OP 的练习。

于 2012-09-07T21:54:08.183 回答
0

此解决方案使用 Python。（版本 2.7 和 3.x 应该可以工作）

>>> from pprint import pprint as pp
>>> def int2bits(n):
    return [(i, '{i:0>{n}b}'.format(i=i, n=n)) for i in range(2**n)]

>>> pp(int2bits(n=4))
[(0, '0000'),
 (1, '0001'),
 (2, '0010'),
 (3, '0011'),
 (4, '0100'),
 (5, '0101'),
 (6, '0110'),
 (7, '0111'),
 (8, '1000'),
 (9, '1001'),
 (10, '1010'),
 (11, '1011'),
 (12, '1100'),
 (13, '1101'),
 (14, '1110'),
 (15, '1111')]
>>>

它找到最大数字的宽度，然后将 int 与二进制格式的 int 配对，每个格式化的字符串在必要时用零填充以填充最大宽度。（pprint 的东西只是为了得到这个论坛的整洁打印输出，可以省略）。

于 2012-09-08T07:53:23.063 回答
0

您可以通过生成从 0 到 2^n-1 的二进制表示的所有整数来实现

static int[] res;
    static int n;
    static void Main(string[] args)
    {
        n = Convert.ToInt32(Console.ReadLine());
        res = new int [n];
        Generate(0);

    }

    static void Generate(int start)
    {
        if (start > n)
            return;
        if(start == n)
        {
            for(int i=0; i < start; i++)
            {
                Console.Write(res[i] + " ");
            }
            Console.WriteLine();
        }

        for(int i=0; i< 2; i++)
        {
            res[start] = i;
            Generate(start + 1);
        }
    }
于 2014-12-04T12:25:37.353 回答