Re: [問題] 遞迴排列-- 避免重複字元的遞迴
前前篇文章用到 link list
許多指標的觀念對新手來說可能比較辛苦
我再提供一個比較簡單的版本
#define MAX_INPUT_SIZE 128
struct ASCII_TBL {
char alpha[256]; // alpha[i] 代表有出現過的第 i 個 character
int nAlpha; // nAplha 代表出現過多少個 character
int freq[256]; // freq[i] 代表 character i 出現的次數
char result[MAX_INPUT_SIZE]; // 用來記錄每次的結果
int inputLen; // 原輸入長度
};
比如說, 以 "c&c++" 為例
先預處理把上述表填完
得到
alpha[0] <= '&'
alpha[1] <= '+'
alpha[2] <= 'c'
nAlpha <= 3
freq['&'] <= 1
freq['+'] <= 2
freq['c'] <= 2
inputLen <= 5
其餘都是零
void recur(struct ASCII_TBL *ascTbl, int lvl)
{
int i;
/* 若已將所有字元都用上了, 輸出結果 */
if(lvl == ascTbl->inputLen)
{
ascTbl->result[lvl] = '\0';
printf("%s\n", ascTbl->result);
return;
}
/* 對每個有出現的字元 */
for(i=0;i<ascTbl->nAlpha;i++)
{
char alpha = ascTbl->alpha[i];
/* 若還沒用完, 則用掉一次 */
if(ascTbl->freq[alpha] > 0)
{
ascTbl->freq[alpha]--;
ascTbl->result[lvl] = alpha;
recur(ascTbl, lvl+1);
ascTbl->freq[alpha]++;
}
}
}
跟原始處理非重複的方法很不一樣的地方在於
我們多了一層取 freq 的選擇
會這樣做是因為每個字元如果出現多次
他們之間的地位都是沒有分別的
所以我們在選擇時只需要知道用了幾次
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.49
推
03/18 11:15, , 1F
03/18 11:15, 1F
※ 編輯: ledia 來自: 140.112.30.49 (03/18 11:17)
推
03/18 14:39, , 2F
03/18 14:39, 2F
推
03/18 15:13, , 3F
03/18 15:13, 3F
推
03/19 00:30, , 4F
03/19 00:30, 4F
推
03/19 00:35, , 5F
03/19 00:35, 5F
推
03/19 00:37, , 6F
03/19 00:37, 6F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 6 篇)：