→ willyhsu:謝謝y大 大感謝! 03/12 19:44
※ 編輯: yauhh 來自: 218.160.212.16 (03/13 00:46)
※ 引述《willyhsu (wi)》之銘言：
: 我的想法是：(以4個attributes為例ABCD)
: 當產生A後，call subset時，會以A為prefix一直遞迴下去，直到換B為prefix遞迴...
: 觀察的結果是：每深度一次，就會多出一個attributes要和原來出現的屬性做結合
: 因此在call subset 要產生AB之前，就會出現B屬性是新屬性沒被處理
: 所以 新屬性B 先產生set(B)的部分，再和已處理過的attribute(A)結合成(AB)
: attributes : A B C D
: 先深度
: A (ok)
: AB (B為新屬性，提前產生B，也就是set(B)，再產生(AB))
: ABC (C為新屬性，提前產生C，和A結合產生(AC)和B結合產生(BC) )
: ABCD (D為新屬性，提前產生D，set(D)先產生D，再和A,B,C結合產生其他長度的組合 )
: 把上面想法實際寫flow chart時，複雜到不知道怎麼變成遞迴的方式進行
: 不知道是這樣產生的次序本來就很不容易找到規則呢?
: 先感謝板上的板友回應 謝謝!
抱歉前一篇文章搞錯了,只做了你已經做過的部份.
你的組合順序是:
先拿到 A, 就取 {A} 對 {} 多出來的的子集得 A.
然後拿到 B, 取 {B} 對 {A} 多出來的子集得 B AB.
再拿到 C, 取 {C} 對 {A,B} 多出來的子集得 C AC BC ABC.
再拿到 D, 取 {D} 對 {A,B,C} 多出來的子集得 D AD BD CD ACD BCD ABCD.
依序拿到 A AB ABC ABCD, 這是最外層的遞迴.
裡層的遞迴是,先遞迴呼叫取得既有元素集合的子集,
然後產生新元素,然後讓新元素和遞迴呼叫來的子集各元素配對.
例如,你已經拿到 ABC, 並且先遞迴呼叫取得 ABC 的子集,
現在產生 D, 然後讓 D 對 {A,B,AB,C,AC,BC,ABC} 配對
得 AD BD ABD CD ACD BCD ABCD. 於是, {A,B,AB,C,AC,BC,ABC}+{D}
+{AD,BD,ABD,CD,ACD,BCD,ABCD} 是 ABC+D 的輸出.
----- 2011/3/12 11:49pm ---
補個實作:
我用 queue 維護集合. 先做 queue 結構: 不外乎
#define QUEUE_SIZE 80
struct Queue {
int front;
int rear;
char** data;
};
void init(struct Queue *q) {
int i;
q->front = -1;
q->rear = -1;
q->data = (char**)malloc(sizeof(char*)*QUEUE_SIZE);
for (i=0; i<QUEUE_SIZE; i++) {
q->data[i] = NULL;
}
}
int next_qindex(int index)
int prev_qindex(int index)
void enq(struct Queue *q, char* str)
char* deq(struct Queue *q)
int is_empty(struct Queue q)
void layout(struct Queue q) {
int i;
if (q.front == q.rear) return;
i = q.front;
do {
i = next_qindex(i);
printf("%s\n", q.data[i]);
} while (i != q.rear);
}
然後我有一個特殊的函數叫作 pair, 把一個元素 e 分別銜接在一個 queue 內容
每個元素之後,會得到另一個集合,所以傳回另一個 queue. 例如: C + {A,B} 得到
{AC,BC}.
struct Queue* pair(struct Queue *q, char e) {
int i;
struct Queue *q1;
q1 = (struct Queue*)malloc(sizeof(struct Queue));
init(q1);
if (q->front == q->rear)
return q1;
i = q->front;
do {
int nlen;
char* nstr;
i = next_qindex(i);
nlen = strlen(q->data[i]) + 2;
nstr = malloc(sizeof(char)* nlen);
strcpy(nstr, q->data[i]);
nstr[nlen-2] = e;
nstr[nlen-1] = '\0';
enq(q1, nstr);
free(nstr);
} while (i != q->rear);
return q1;
}
最後,主要的遞迴部份是 sos 函數,
如果處理 ABCD 時, 先求 sos(ABC) 得到一個集合 q ,
再對 sos(ABC) + D 求另一個集合 q1 (使用 pair 函數).
當然別忘了要先 enque D, 然後把 q1 的元素一個一個 enque 到 q 即可.
void sos(struct Queue *q, char* set, int lset) {
if (lset <= 0) {
return;
} else {
char estr[2];
struct Queue *qsubset;
sos(q, set, lset-1);
estr[0] = set[lset-1];
estr[1] = '\0';
qsubset = pair(q, set[lset-1]);
enq(q, estr);
while(!is_empty(*qsubset)) {
char* nstr = deq(qsubset);
enq(q, nstr);
free(nstr);
}
}
}
int main() {
struct Queue queue;
char set[4] = "ABCD";
int lset = 4;
init(&queue);
sos(&queue, set, lset);
layout(queue);
return 0;
}
執行的狀況:
$ gcc -o sos1 sos1.c;./sos1
A
B
AB
C
AC
BC
ABC
D
AD
BD
ABD
CD
ACD
BCD
ABCD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.212.16