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

[yauhh (喲)]

※ 引述《willyhsu (wi)》之銘言：
(略)
: 問題(Question)：
: 計算資料所有的組合和其出現的次數
: 目前寫法是以深度優先產生所有組合(目前已完成)，但是要改成當深度下去時
: 當有子集未被產生，會先產生子集的部分才能產生超集的部分
: 比方： 總共有4個attributes A,B,C,D
: 目前深度產生方式： A, AB, ABC, ABCD, ABD, AC ,ACD, AD, B...
: 改成當AB要產生時，因為B還沒被產生，所以必須先產生B才能產生AB

有點疑惑,為什麼你覺得深度搜尋是還沒用到 B 就不要先產生 B ?
深度搜尋應該是先存在一顆樹,不管那是概念上的或真的有那個樹結構,
反正樹節點可以先存在,然後你隨時可以去搜尋.

先說我看到這題目最初的解法: 要準備一個 stack, 然後,

1. 先處理 A, 這時要把 {A,B,C,D} 大於 A 的項目都放進堆疊,
   是以項目由大到小依序放進堆疊 .
                                     |DCB
   這些元素之後取出來,會是同一層級的平輩節點.

2. 接下來要關心子節點. 目前有 A, 所以對 {B,C,D} 這些大於 A 的元素,
   也就是大於手上元素最後一項的元素,挑出最小的項目,在此挑 B.

   挑了 B 之後得到 AB, 要再進行 1. 程序,但對象是 B,
   把大於 B 的項目都照特定順序放進堆疊做為目前 B 的平輩節點,
   堆疊的情況為:
                                    |DCBDC

3. 程序 1. 2. 很顯然是一對遞迴程序. 在此暫停一下,來看什麼叫作遞迴:

遞迴是指大結構的問題套疊或拆結為小結構的問題,而大小結構都是一模一樣,
所以解決問題的程序不但可以套用在大結構的問題,也可以適用於小結構的問題.
而且,對於遞迴,我們還要關心另一方面是,所處理的小結構問題是不是可以拆解到
最後,問題小到可以使遞迴程序結束.

   回頭繼續講程序 3. ,既然程序 1. 2. 是一對遞迴程序,要怎麼使遞迴停止?

   首先我有 {A,B,C,D}, 經過程序 1. 然後程序 2. ,手上有 AB, 剩下 {C,D}.
   接著再做程序 1. ,手上有 ABC, 剩下 {D}. 到最後會發現手上有 ABCD,
   然後當我在程序 2. 要挑大於 D 的最小項元素時,卻挑不到東西,因為剩下 {}.
   這就代表一個結尾. 所以程序 2. 可以修正為:

2. 接下來要關心子節點. 目前有 X_1,X_2,...X_i, 所以對 {X_i+1,X_i+2,...,X_n}
   這些大於 X_i 的元素可以挑出最小的項目 X_i+1 做為 X_i 的子節點.
   當挑出 X_i+1 的瞬間,執行程序 1.

以上 1. 2. 為向前搜尋的動作. 接著,必定要處理倒退的動作. 在程序 1. ,因為有
把一些分歧點放進堆疊,就像是把麵包屑沿路丟下做記號,順著記號倒退到前一個岔路,
就可以找到下一個搜尋的去處了.

4. 因為剩下 {}, 只好根據手上的 ABCD 回頭,直接把最後一個, D, 丟掉,剩下 ABC.

5. 由於程序 4. ,已經退到 ABC, 但 C 是分歧點所以丟掉, 剩下 AB. 再看看
   堆疊,此時是
                        |DCBDCD
   所以取出 D, 堆疊剩下
                        |DCBDC
   而手上得到 ABD.

   接下來是一個新的開始,請走程序 1.

程序 4. 5. 然後程序 1. 2. ,這整個看起來也是遞迴程序. 基本上是 1. 2. 遞迴,
有時諱言伸出 4. 5. 接下來問題就是,包含了程序 1. 2. 4. 5. 的遞迴要怎麼結束?

還記得,遞迴程序 1. 2. 的底是當已經沒有大於手上最後一個項目的元素時,遞迴結束.
這是處理子節點的部份.

至於遞迴程序 1. 2. 4. 5. 就要處理到平輩節點, 而我們用 stack 處理平輩節點,
所以想當然是當 stack 清空了,完整的遞迴程序就結束了.


----------------

這樣寫好長喔, 先休息一下.


----------------

接下來是實作. 我用 C 語言來實作.

首先, stack 是一定要寫的,先列個綱要,細節省略:

#define STACK_SIZE 80

struct Stack { int top; char data[STACK_SIZE]; };

void init(struct Stack *s)
void push(struct Stack **s, char data)
char pop(struct Stack *s)
int is_full(struct Stack s)
int is_empty(struct Stack s)
int size(struct Stack s)

在程序 1. 需要處理平輩節點. put_siblings 函數將大於某元素的集合取出,
反序放入堆疊:

void put_siblings(struct Stack **s, char e, char* a, int l) {
  int i, j;
  for (i=0; e>=a[i]&&i<l; i++);
  for (j=l-1; j>=i; j--) {
    push(s, a[j]);
  }
}

以上其中 e 是比對元素, a 是集合, l 是集合陣列長. a 陣列內定為由小排到大
的字母,使用時請自行手動排序.

在程序 2. 我需要取陣列的最後一個元素:

char last(char* a, int l) {
  return a[l-1];
}

另外還要有一個 min_of_greater 函數, 求大於指定元素的最小元素:

char min_of_greater(char e, char* a, int l) {
  int i;
  for (i=0; e>=a[i]&&i<l; i++);
  return (i == l)? 0: a[i];
}

以上其中可能有找不到項目的狀況, 用傳回 0 表示找到空集合 {}.

基本工作定好了,遊戲就開始了. 首先,向前搜尋我取名為 breed (繁殖),
程式大意是說: 對任一非空字串 str (長度為 lstr), 其目前的字串組合可以印出.
然後由程序 2. 找大於最後一個字母 (以 last 函數取最後一個字母) 的集合中
最小元素 (由 min_of_greater 求之), 如果找出空集合 (由 0 表示找出的是空集合)
就進行程序 4. 5. 然後 1. 等等.  否則如果找得到大於最後一個字母的最小元素,
就把找出的最小元素當作子節點,同時把大於這個新的子節點的其他集合元素推入堆疊
(由 put_siblings 進行), 然後遞迴進行 breed 函數.

void breed(char* str, int lstr, char* set, int lset, struct Stack *s) {
  char last_char, mog;
  void backtrack(struct Stack *s, char* str, int lstr, char* set, int lset);
  printf("%s\n", str);
  last_char = last(str, lstr);
  mog = min_of_greater(last_char, set, lset);
  if (mog == 0) {
    backtrack(s, str, lstr, set, lset);
  } else {
    lstr = lstr + 1;
    str[lstr-1] = mog;
    str[lstr] = '\0';
    put_siblings(&s, mog, set, lset);
    breed(str, lstr, set, lset, s);
  }
}

下一段是程序 4. 開始的 backtracking. 我取名為 backtrack 函數:

void backtrack(struct Stack *s, char* str, int lstr, char* set, int lset) {
  int stack_size;
  stack_size = size(*s);
  if (stack_size == 0) {
    return;
  } else {
    char ch;
    lstr = lstr - 2;
    str[lstr] = '\0';
    ch = pop(s);
    lstr = lstr + 1;
    str[lstr-1] = ch;
    str[lstr] = '\0';
    breed(str, lstr, set, lset, s);
  }
}

在 backtrack 函數中,我認定 stack 如果清空了,就可以結束所有的工作.
而如果堆疊有東西,另外還要有一個前置狀態為手上的資料起碼有二個可以刪掉,
意思是先退後一個節點,刪掉一個分歧點,然後從堆疊中找下一個點做新的分歧點.

當然,程式一開始的狀態是: 手上有一個點 A, 堆疊中已經放好   |DCB   ,
並且集合列表的字母是排序的. 如主程式:

#define STRING_LEN 80
#include <stdio.h>
#include <stdlib.h>

int main() {
  char str[STRING_LEN] = "A";
  int lstr = 1;
  char set[4] = "ABCD";
  int lset = 4;
  struct Stack *stack = malloc(sizeof(struct Stack));
  init(stack);
  put_siblings(&stack, str[0], set, lset);
  breed(str, lstr, set, lset, stack);
  return 0;
}

----------------------

執行情況:

----------------------
$ gcc -o sos sos.c;./sos
A
AB
ABC
ABCD
ABD
AC
ACD
AD
B
BC
BCD
BD
C
CD
D


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.160.212.16
→ tropical72:y大執行結果似乎不是原po想要,在 A 到 AB 時，因 B 還
→ tropical72:沒被生成,於是要 A->B->AB->C->ABC, 不知是否我誤會了.
→ bleed1979:其實這題不太需要遞迴，如果硬要弄一個，以下是解法。
→ bleed1979:http://nopaste.csie.org/cc944
→ yauhh:ok. 另外,當人的需求是遞迴的時候,不要修改人的需求.
→ yauhh:原po明確講了要遞迴解,所以,你應該提供遞迴解而不是非遞迴解
→ bleed1979:請教樓上認知的遞迴是什麼？程式碼是把非遞迴改遞迴。
→ willyhsu:謝謝T大 就是當子集還沒被產生時 要先產生子集的部分
→ willyhsu:有些問題想請問b大, recur()的21行else這部分我不是很清
→ willyhsu:楚，它的邏輯是什麼。另外當SIZE超過13就會時間變很長，
→ willyhsu:這是因為遞迴才拖慢速度嗎?
→ yauhh:遞迴是許多問題的基本結構,而不是特地為了製造遞迴而遞迴.
→ yauhh:舉例來說,某個比例的直角三角形,從直角的垂線切開,會得到
→ yauhh:兩個同形的三角形,這樣的結構就叫作遞迴. 遞迴是因為它自然
→ yauhh:存在,所以你可以找到最自然的遞迴解法.
→ yauhh:另外,原po所貼程式碼及問題描述,並不是把非遞迴改成遞迴.
→ yauhh:他的問題是想把一種輸出順序改成另一種輸出順序,而且他程式
→ yauhh:已經寫好的部份,見subset,是遞迴程式.