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

[yauhh (喲)]

※ 引述《bleed1979 (十三)》之銘言：
: 這題我覺得原po需要把問題描述得更清楚一些，
: A
: B
: AB
: C
: AC
: BC
: ABC
: D
: AD
: BD
: ABD
: ^^^^
: CD
: ^^^^
: ACD
: ^^^^
: BCD
: ABCD
: 請注意看標記的部分，跑到D的時候，ABC已經先出現了，
: CD是否應該優先於ABD？　如果不必，只是把前述的結果加個D，

如果重點是在 "存在論", 則細節的產生順序不重要.

用一點 proof tree 來說明,如下圖:

        W |- A    W + {B} |- B
      -------------------------
        W + {B} |- {A,B,AB}       W + {B,C} |- C
      -------------------------------------------
        W + {B,C} |- {A,B,AB,C,AC,BC,ABC}          W + {B,C,D} |- D
      ------------------------------------------------------------------
        W + {B,C,D} |- {A,B,AB,C,AC,BC,ABC,D,AD,BD,ABD,CD,ACD,BCD,ABCD}

當你把 D 放進這個世界時,要考慮如何產生新的組合,
但是 {A,B,AB,C,AC,BC,ABC} 的順序如何,不是在 D 生成時決定的.
那些都是在 D 之前已經存在了.

所以,你在看 CD 可不可以放到 ABD 的前面時,要看看假如還沒有 D, C 可不可以放在
AB 前面. 由 proof tree 第二層可知, 是 AB 先存在了,所以 C 並沒有理由放到 AB
前面,並且因此 CD 沒有理由放到 ABD 前面. 不過,這樣是考慮到如果順序真的很重要.
而集合跟 ordered list 概念有所差異. 就集合來說,當你把一個新東西加到世界中,
瞬間產生的新組合各項的順序是不重要的.

你說原po應該把問題描述清楚,我卻覺得你所指的該描述清楚的那個東西
是原po所提的這個遞迴問題的答案. 原po提了一個問題,問,他想要按照各項目
存在的順序產生所有的組合,那麼在這個綱要之下, ABD, CD, ACD 的順序為何,
應該要由回答問題的人來解.

--------

抱歉,太哲學了. 掰掰.


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

: 推 Ebergies:列舉所有組合本來就是這樣, 每多一個 symbol 就多一倍     03/13 19:4
: → Ebergies:這也是為何 x= 0~N, SUM( C( N, x))= 2^N 的原因          03/13 19:4
: → Ebergies:而且這題目用迴圈會比用遞迴直覺很多                     03/13 19:5

這樣講就好玩了,現在這個題目是:

        請產生 {A,B,C,D} 的子集,使子集生成順序滿足以下條件:
        1. A, B, C, D 依序生成.
        2. 任一子集必須在其超集之前生成.

請說明使用迴圈有何直覺?

我認為在這題使用迴圈根本不直覺. 如果使用迴圈,你要先把產生的子集全都列出來
觀察一次,然後想辦法拼湊出各種參數,什麼 flag 或者 swap 規則之類的,想辦法
把答案拼湊出來. 但是 flag 和各種交換的規則都是除了這個問題本身之外額外添加的
資訊. 用迴圈做,是加油添醋去做出目前你要的答案; 等到將來題目稍微改變,
或者處理的輸入資料稍有改變,你還要設法加油添醋把程式改到保證能產生新的結果.

然而,使用遞迴解決則非常直覺: 對 {A,B,C,D} 我知道最後一個子集是 ABCD;
並且我知道一條遞迴規則是,因為 ABCD 的子集都必須在 ABCD 之前產生,而只要
把 ABC 的全部子集的每一個都加上 D 所得的集合加入 ABC 的全部子集,就會得到
ABCD 的全部子集. 而 ABC 全部子集的產生可仿照 ABCD 子集的產生.
所以當我寫這個程式,我只思考子集的處理,至於子集的生成全都由程式做出來.
我不必特地把程式寫成某種特別的奇形怪狀去勉強做出答案.


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.212.16
※ 編輯: yauhh           來自: 218.160.212.16       (03/13 20:53)
→ bleed1979:抱歉，y大，我說的原po就是指提問題的人。
→ bleed1979:另外，當用資料結構儲存之前產生的結果時，
→ bleed1979:我就會去思考遞迴的必要性，這題有點是為遞迴而遞迴。
→ yauhh:對啊,我的原po也是指提問題的人. 我說的是你說題目不明確.
→ yauhh:但是,很多時候問問題都是不明確的,因為那個不明確的部份稱為
→ yauhh:"答案".
→ yauhh:哦,我非常好奇像這個題目,你如何在沒遞迴資訊的時候直接生出
→ yauhh:解答的步驟?