Re: [問題] 遞迴產生組合問題

[bleed1979 (十三)]

這題我覺得原po需要把問題描述得更清楚一些，

A
B
AB
C
AC
BC
ABC
D
AD
BD
ABD
^^^^
CD
^^^^
ACD
^^^^
BCD
ABCD

請注意看標記的部分，跑到D的時候，ABC已經先出現了，

CD是否應該優先於ABD？　如果不必，只是把前述的結果加個D，

那我提供使用global的STL的以下不到40行的程式。

#include <iostream>
#include <vector>
using namespace std;

const int SIZE = 3;
vector< vector<char> > Subset;

void output(vector<char> &vec) {
    vector<char>::iterator it = vec.begin();
    while(it != vec.end()) {
        cout << *it;
        ++it;
    }
    cout << endl;
}

void recur(int d) {
    if(d >= 0) {
        recur(d - 1);

        int sz = Subset.size();

        vector<char> new_vec;
        new_vec.push_back(char(d + 'A'));
        output(new_vec);
        Subset.push_back(new_vec);

        for(int i = 0; i < sz; ++i) {
            vector<char> old_vec(Subset[i]);
            old_vec.push_back(char(d + 'A'));
            output(old_vec);
            Subset.push_back(old_vec);
        }
    }
}

int main() {
    recur(SIZE);
    return 0;
}


如程式碼運行一樣，你只需一直先遞迴到底，

之後在對上一層的所有結果增加一個字元。

這樣題目就變得簡單了。


Bleed


※ 引述《yauhh (喲)》之銘言：
: ※ 引述《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: 114.25.244.234
推 Ebergies:列舉所有組合本來就是這樣, 每多一個 symbol 就多一倍
→ Ebergies:這也是為何 x= 0~N, SUM( C( N, x))= 2^N 的原因
→ Ebergies:而且這題目用迴圈會比用遞迴直覺很多
→ loveme00835:STL一直都不是 global 的喔~ ^^"
→ bleed1979:其實我想表達把容器設成全域的懶得傳來又傳去的意思。
→ firejox:列舉的所有組合可以想成每個數只有兩種選擇
→ firejox:所以是2^N