C 中所有可能的组合

Question

我试图在 C 中找到一种有效的算法，它为我提供给定字符集的所有组合。

该算法不应该递归。最后，位数应该是灵活的。例如：

char set[] = "a1";
->
a1
aa
1a
11

我只找到了一个 Perl 解决方案，但它使用 substr()。我认为这在性能方面并不是那么快。

对于大多数 C 算法，我发现只是排列...

德国 C++ 论坛上的一篇文章声称，C++-STL 解决方案比“原始”递归算法更快。

Answer 1

如果集合大小是固定的 N，那就很简单 - 您可以只有 N for 循环，每个循环都嵌套在前一个循环中。由于你不能这样做并且不能使用递归，所以你必须计算所需的总迭代次数（似乎是 N^M），使用一个循环，然后使用 / 和 % 来计算数组索引每个字符应该是。你最好也使用长整型，因为 N^M 变大的速度很快。

Answer 2

维基百科有 n 进制格雷码 的 C 代码。通过使用数字作为输入数组的偏移量，它应该可以转换为您的问题。您将需要进行一些动态分配来处理任意长度的输入。一种相关的方法是进行嵌套循环，其中有一个与输入一样长的循环计数器数组，以及当前正在递增的另一个计数器。例如，打印所有六位数的六进制数字，需要修改为动态分配，但显示了原理：

int i;
int length = 5;
int max = 6;
int counters[length];
for (i=0; i<length; i++)
    counters[i] = 0;
for(;;) {
    for (i=length-1; i>=0; i--)
        printf("%d", counters[i]);
    printf("\n");
    for(i=0; i<length; i++) {
        counters[i]++;
        if (counters[i] < max)
            break;
        else
            counters[i] = 0;
    }
    if (i >= length)
        break;
}

Answer 3

Python 非常接近于伪代码。

您可以阅读 Python 源代码 itertools.permutations 并在 C 中复制这

是有效的演示：

#!/usr/bin/env python
import itertools

s='a1'

print set(itertools.permutations(s*len(s), len(s)))

输出：

set([('1', '1'), ('a', '1'), ('a', 'a'), ('1', 'a')])

这是一种更简单的方法：

>>> s='a1'
>>> ['{}{}'.format(x,y) for x in s for y in s]
['aa', 'a1', '1a', '11']


>>> s='abc'
>>> ['{}{}{}'.format(x,y,z) for x in s for y in s for z in s]
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 
 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 
 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 
 'cca', 'ccb', 'ccc']

要展开列表理解，请使用嵌套循环，如下所示：

>>> for x in s:
...    for y in s:
...       for z in s:
...          print '{}{}{}'.format(x,y,z)

Answer 4

好吧，我会对可能的组合进行编号，循环遍历数字并进行转换。

例如：要生成 10 个符号 {'0', '1', ..., '9'} 的所有大小为 3 的组合，我将从 0 到 999 循环并输出“000”到“999”。

以同样的方式（有点），要生成 5 个符号 {'a', 'b', ..., 'e'} 的所有大小 3 的组合，我将从 0 循环到 5*5*5-1 并输出以 5 为基数的循环编号，但带有提供的符号。

Answer 5

编写一个函数，将整数转换为字符串十六进制数字，然后将该算法转换为基数 36（az 加 0-9）数字。使用一个 for 循环从 1 计数到（数字计数乘以基数）并每次调用您的函数。

• 1 变为 1
• 10 变为 a
• 35 变为 z
• 36 变为 10
• 46 变为 1a