如何枚舉長度為n的所有字符組合

             
如何枚舉長度為n的所有字符組合
--------------------------------------------------------------               
可用來生成密碼字典,純做技術研究

1. 對於一個長度為n的密碼字串來說,每一位都有0-255種選擇.
可用一個狀態表來表示
char[n], n={0,1,2,3,......}
那麼一共有 255*255*255*255*...種狀態,
全部列出是一個天文數字.


2. 如果將選擇範圍縮小,只選小寫英文字母(26).
長度為5的口令有 26^5 (11881376)種選擇 .


3. 用所有的的大,小寫字母,數字來組和n位口令,一共有 (26+26+10)^n 種選擇.
如果n不大,完全可以用計算機試出來.


4. 設char[n]為一狀態表, 長度為n, 每一位有m種選擇.
  這時可將char[n]看做m進制的數據.
  每加1,狀態改變一次,


5. 如何將狀態表生成密碼字串呢 ?
  每一位對應字符表中的一個字符.
  如char[1] = 11  :表示第一個字符是字符表中的第11個字符.
    char[2]= 5  :表示第二個字符是字符表中的第5個字符.
  依此類推

 
6. 退出條件.
  測試溢出位為  1時退出
 
 
7. 其它.
  如果第一位的的選擇是a-z
  第二位: 0-9
  第三位: A-F:
那麼也是可以的.
只需要每一位對應一個字符列表,
每個一位的最高狀態為列表長度.

簡單版本1.每一位的可能組合都一樣
stack2.c 每一位都可以是不同的組合.
利用int  str_allcase(char *text)可以生成一字串的所有不同大小寫組合


下一步該如何增強?
試著用regex的語義來生成字典表.
這樣就可以輸入 test  [a-z]{2}[0-9]  這的方式來列出所有的組合了.

 

所有code在附檔

文件:	stack.tar.gz
大小:	1KB
下载:	下载

版本1.的code

#include
#include
#include
/*
m 進制數據加 1

 */
void  calc_inc(int  calc[],int max)
{
         int i =  0;
     /*
        over[i] == max :    該位已達最高狀態
     */
     for (; calc[i] == max ; i++ ) {
         calc[i] =0 ;

     }

     calc[i] ++;
}





void put_buf(char *dest,  int size,  char *base, int calc[])
{
         int i;
     for (i=0; i             dest[i] = base[calc[i]] ;
     }
}

#define BSIZE 30
/*
 *類似於 N 進制數據
 *
*/

int gen_dict(char *base, int outsize)
{
     int i ;

     int   level = strlen(base);

         int   calc[BSIZE] ;
     int   overflag[BSIZE] ;  /*just for test  */
     
     for (i=0; i             calc[i] =0;
         overflag[i] = level -1 ;
     }

     int *overbit =& (calc[outsize]) ; /*    溢出位 */

     char outbuf[BSIZE] ={0};
     while (*overbit == 0)  {
             put_buf(outbuf,outsize, base, calc);
             fprintf(stdout,"%s\n", outbuf);
         calc_inc(calc, level-1);
     }
     return (0);
}


int main(int argc, char *argv[])
{

         char *data1= "abcdefghijklmopqrsturvwxyz" ;
         char *data2= "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
         char *data3= "0123456789";
   
     gen_dict(data3,4);
     exit(0);

}

編譯運行.
輸出效果類似如下.
./test
AAAA
BAAA
CAAA
DAAA
EAAA
FAAA
GAAA
HAAA
IAAA
JAAA
KAAA
......

./stack |wc -l
共生成456976個字串.
耗費時間如下, 應該可以優化一下的
./test >/tmp/aa.txt
real    0m0.296s
user    0m0.284s
sys     0m0.008s

 阿飛
2007/11/21