algorithm - 生成 k 个字符的大小 n 个组合的算法

Question

我需要一种算法来生成 k 个字符的大小 n 的所有组合。

例如，如果我有 n=1 和 k={a,b}，则结果应该是：

a
b

如果 n=3 且 k={a,b}，则结果应为：

a a a
a a b
a b a
a b b
b a a
b a b
b b a
b b b

有人可以建议一种算法来实现这一点吗？

谢谢！

Answer 1

您可以简单地将您的解决方案映射到值 0 到 (|k|^n )-1。解只是以 |k| 为基数的数字的表示。

例如 k={a,b,c} n=2
解是 0,1,2,... 3^2 -1 = 8

decimal |  representation in base 3
--------+---------------------------
0       |   00
1       |   01
2       |   02
3       |   10
4       |   11
5       |   12
6       |   20
7       |   21
8       |   22

现在用“a”替换“0”，用“b”替换“1”，用“c”替换“2”，你得到

aa
ab
ac
ba
bb
bc
ca
cb
cc

Answer 2

k 的 n 次方的长度

在java中：

int combinations = Math.pow(k.length,n);

Answer 3

我就是这样做的。
它很直观，希望对您有所帮助。说明：选择一个字符并选择放在它旁边的内容。递归地执行此操作。

 char availablechars[];//In your case this is {a,b}
 int availablechars_size;//This is 2
 void generate(int n,string res)
 {
   if(n==0)
   {
     cout<<"\n"<<res;
     return;
   }
   for(int i=0;i<availablechars_size;i++)
   {
    string t=res;
    t+=availablechars[i];
    t+=" ";
    generate(n-1,t);
   }
 }

时间复杂度：O(k ⁿ )

函数调用是：

 generate(n,"");