最近做一個東西正好需要生成字典的算法，類似一些密碼字典生成器(主要運用在暴力破解)。生成的密碼會根據密碼長度與字典集合的長度成指數關系。
可以用一個函數來表示
f( x , y ) = x ^y ; x表示我們要生產的密碼長度，y表示我們要生成的密碼字典字符集合。
當時想到就有3個算法。
1.循環
關于循環，可以參考水仙花數的多層嵌套求解，主要算法如下:
1
/**//// Dict 為生成的密碼 ， g_Dict為字典集合 2
for ( int i = 0 ; i < Len ; i++ )
3
{
4
Dict[0] = g_Dict[i];
5
6 for ( int j = 0 ; j < Len ; j++)
7
{
8 Dict[1] = g_Dict[j];
9
10 for ( int k = 0 ; k < Len ; k++ )
11 {
12 Dict[2] = g_Dict[k];
13
14 /**//*
15 * 幾位密碼就嵌套幾層循環
16
*/
17
18 }
19 }
20
}
這種方式移植不好，而且代碼臃腫。
2.遞歸
做過字符串的全排列的都明白這個算法，這種也是基于這種方式：但是由于隨著字典集合或者密碼長度的增加，很容易會出現堆棧的內存溢出。
1void solve(int len,int p , int s,int n)
2{
3 int i;
4 if( s == n )
5 {
6 /**////std::cout << Dict << std::endl;
7 return ;
8 }
9 if(s>n||p>n)
10 return;
11 for( i=p ; i < len ; i++ )
12 {
13 solve(len,i+1,s+1,n);
14 }
15}
3.BFS
有了前2種方法的不錯，然后寫了一個非遞歸的算法
主要借用橫向掃描的方式，借鑒一個數組來進行記錄當前應該生成的密碼。
主要算法如下:
1/**//*
2* 生成字典的函數
3* @parm 需要生成的長度
4*/
5void MakeDict( int Len )
6{
7 char Dict[MaxDictLen+1]; // 生成的字典字符串
8 int Array[MaxDictLen]; // 記錄當前應該生成字典數組
9
10 memset( Array , 0 , sizeof(Array) );
11
12 bool bStop = true;
13
14 int i,j;
15 for ( ; bStop ; ) // 是否生成完畢
16 {
17 for ( i = 0 ; i < Len ; i++ )
18 {
19 Dict[i] = g_Dict[Array[i]];
20 }
21 Dict[Len] = '\0';
22
23 std::cout << Dict << std::endl;
24
25 /**//// 字典數組坐標更新
26 for ( j = Len - 1 ; j >= 0 ; j -- )
27 {
28 Array[j] ++ ;
29
30 if ( Array[j] != ((int)g_Dict.length()) )
31 {
32 break;
33 }
34 else
35 {
36 Array [j] = 0;
37 if( j == 0 ) // 生成完畢
38 bStop = false;
39 }
40 }
41 }
42}
附上第三個生成算法源碼:
link