→ walker2009:一個很暴力的方法是用hash記下哪個曾經出現過... 03/16 16:08
→ walker2009:另外一個方法是給予同樣的 symbol 編號 03/16 16:09
→ walker2009:如 #1 #2 #3 03/16 16:09
→ walker2009:而在做遞迴排列時增設條件, 條件是 03/16 16:09
→ walker2009:同樣的 symbol 編號小的一定要在編號大的前面 03/16 16:10
→ walker2009:沒細想, 應該可行, 有問題有其他高手版大會幫忙提出XD 03/16 16:11
→ cutecpu:###1 照樓上的方法可以排出 #1## 嗎 03/16 18:05
→ walker2009:樓下V大 03/16 18:16
→ liu2007: 可以請教一下Y大是怎麼做的嗎@.@? 03/16 20:17
→ YesIam118:遞迴只應118用, 凡人該當用迴圈. 03/16 21:00
→ walker2009:樓下V大 03/16 22:08
推 F23ko:好像很有趣....我想想看 03/16 22:22
推 walker2009:樓下V大 03/16 22:29
推 F23ko:寫出來了 =.= 03/17 00:15
推 F23ko:原po已經寫出用遞迴列出"會重覆"的排列了嘛 03/17 00:36
→ F23ko:關鍵在於.... 要寫個區域陣列變數，記錄下自己已經用過的字 03/17 00:37
→ F23ko:母，只要不用同樣的字母下去跑，就ok了 03/17 00:37
→ F23ko:如果你想看C#的程式碼 我可以寄給你.... C++我忘很久了 = = 03/17 00:39
> -------------------------------------------------------------------------- <
作者: yauhh (喲) 看板: C_and_CPP
標題: Re: [問題] 遞迴排列-- 避免重複字元的遞迴
時間: Thu Mar 18 07:54:22 2010
※ 引述《liu2007 (薯)》之銘言：
: 我打算用遞迴寫字元的排列
: 可是這個字元陣列裡有時候可能會有重複的情況
: 譬如說
: a b c d e f # #
: 當這八個字元下去做排列的時候
: 理應只有 8!/2! 的答案
: 但是對於電腦來說還是有8!個答案
: 請問要怎麼樣避免這種狀況發生??
: 可否題點一下解決的方法@.@?
: 使用遞迴實在是好難......
遞迴概念超簡單,但用C寫實在是很難抓住細節,會寫到很想殺幾個人...
取字串排列會用到一個函數,是給一個字元a和一個字串str,求將a插入str任二個
字元之間,或是放在str頭或尾,的全部可能的結果.
在此稱這個函數是poss_insert.
一開始先寫個全部插入情況的基本型,這是當輸入字元和字串有重覆字母時,
會有重覆結果的情況.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list {
char* str;
struct list* next;
};
struct list* poss_insert(char a, char* str, struct list** ls);
int main(int argc, char *argv[])
{
struct list* ls;
poss_insert('#', "a#", &ls);
int i;
struct list* p = ls;
while (p != NULL) {
printf("%s\n", p->str);
p = p->next;
}
system("PAUSE");
return 0;
}
struct list* poss_insert(char a, char* str, struct list** ls) {
int slen = strlen(str);
if (slen == 0) {
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
(*ls)->str[0] = a;
(*ls)->str[1] = '\0';
(*ls)->next = NULL;
} else {
/* Let a be after str */
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
strcpy((*ls)->str, str);
(*ls)->str[slen] = a;
(*ls)->str[slen+1] = '\0';
/* Let a insert into str */
char* tstr = (char*)malloc(sizeof(char)*(slen-1));
strncpy(tstr, str, slen-1);
tstr[slen-1] = '\0';
poss_insert(a, tstr, &(*ls)->next);
free(tstr);
struct list *p = (*ls)->next, *r;
char* q;
while(p != NULL) {
q = &(str[slen-1]);
p->str = strcat(p->str, q);
p = p->next;
}
}
return (*ls);
}
以上程式中,在先直接把a放到str後面的程式段落,可以發現如果a與str的最後一字
相同,這個動作可以跳過. 因為此時做這個動作,是製造出重覆結果的關鍵步驟.
所以,無重覆版本改成以下情況,改法是在發現a是str最後一字時,把struct list
結構的當前節點當做是空節點. 是藉著將 (*ls)->str 指定為 NULL 方式.
而這樣修改,其他用以讀取串列並產生輸出的程式都要記得檢查 ->str == NULL 情況.
int main(int argc, char *argv[])
{
struct list* ls;
poss_insert('+', "c&c+", &ls);
int i;
struct list* p = ls;
while (p != NULL) {
if (p->str != NULL) {
printf("%s\n", p->str);
}
p = p->next;
}
system("PAUSE");
return 0;
}
struct list* poss_insert(char a, char* str, struct list** ls) {
int slen = strlen(str);
if (slen == 0) {
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
(*ls)->str[0] = a;
(*ls)->str[1] = '\0';
(*ls)->next = NULL;
} else {
/* Let a be after str */
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
if (str[slen-1] == a) {
(*ls)->str = NULL;
} else {
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
strcpy((*ls)->str, str);
(*ls)->str[slen] = a;
(*ls)->str[slen+1] = '\0';
}
/* Let a insert into str */
char* tstr = (char*)malloc(sizeof(char)*(slen-1));
strncpy(tstr, str, slen-1);
tstr[slen-1] = '\0';
poss_insert(a, tstr, &(*ls)->next);
free(tstr);
struct list *p = (*ls)->next, *r;
char* q;
while(p != NULL) {
q = &(str[slen-1]);
if (p->str != NULL) {
p->str = strcat(p->str, q);
}
p = p->next;
}
}
return (*ls);
}
以上主程式情況,輸出:
c&c++
c&+c+
c+&c+
+c&c+
請按任意鍵繼續 . . .
--
媽,我寫出來了! (揮手)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.215.90
※ 編輯: yauhh 來自: 218.160.215.90 (03/18 07:57)
> -------------------------------------------------------------------------- <
作者: ledia (下班後才下棋) 看板: C_and_CPP
標題: Re: [問題] 遞迴排列-- 避免重複字元的遞迴
時間: Thu Mar 18 11:09:56 2010
前前篇文章用到 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) 03/18 11:15
※ 編輯: ledia 來自: 140.112.30.49 (03/18 11:17)
> -------------------------------------------------------------------------- <
作者: cutecpu (可愛中央處理器) 看板: C_and_CPP
標題: Re: [問題] 遞迴排列-- 避免重複字元的遞迴
時間: Thu Mar 18 11:05:17 2010
不知道你原本是用兩兩交換的方式來排列的嗎??
如果是的話，要處理重複只要加個 flag array 即可
如下 code: (紅色標起來的即是處理重複所加上的)
#include<stdio.h>
#include<string.h>
char str[BUFSIZ];
int count;
void perm(int index){
int i;
int flag[128]={0};
char tmp;
if(index){
for(i=index;i>=0;--i){
if(flag[str[i]]) continue;
flag[str[i]]=1;
tmp=str[index];
str[index]=str[i];
str[i]=tmp;
perm(index-1);
tmp=str[index];
str[index]=str[i];
str[i]=tmp;
}
}
else{
++count; /* do nothing, just count */
}
}
void main(){
scanf("%s",str);
perm(strlen(str)-1);
printf("%d\n",count);
}
※ 引述《liu2007 (薯)》之銘言：
: 我打算用遞迴寫字元的排列
: 可是這個字元陣列裡有時候可能會有重複的情況
: 譬如說
: a b c d e f # #
: 當這八個字元下去做排列的時候
: 理應只有 8!/2! 的答案
: 但是對於電腦來說還是有8!個答案
: 請問要怎麼樣避免這種狀況發生??
: 可否題點一下解決的方法@.@?
: 使用遞迴實在是好難......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.248.4.114