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

「0」を「a」に、「1」を「b」に、「2」を「c」に置き換えると、

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,"");