Re: [問題] 遞迴排列-- 避免重複字元的遞迴

[ledia (下班後才下棋)]

  前前篇文章用到 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
推 cutecpu:推！(Y)
※ 編輯: ledia           來自: 140.112.30.49        (03/18 11:17)
推 DJWS:記得檢查一下: 這一層選的字元不會是上一層選的字元
推 DJWS:喔...我想錯了  上面當我沒有推
推 softwind:看起來是為了 thread-safty 才包結構的吧 還是讀code...
推 softwind:                                       還在
推 softwind:看懂了 呵呵 還滿有趣的 次數算是shortcut吧?