[問題] 取有N個元素陣列的子集合

看板C_and_CPP作者 (Firedupandreadytoserve )時間12年前 (2013/05/14 16:31), 編輯推噓5(5推 0噓 29→)
留言34則, 11人參與, 最新討論串1/1
標題好像有點數學上的問題...= = 比方說送一個N值 造出一個{1,2,3,...,N}的陣列當作一個集合 希望能輸出所有的子集合 我的想法是 既然子集合的元素會比較少 那我只要從原本的挖掉 或者填入空白就可以了 如果要填入一個空白 for 0~N-1的位置挖掉就可以了 這很簡單... 填入兩個空白 用for{for{}} 第二層的for只要讓它的指標都指在 比第一層大的位置就不會有重複的結果 這好像也很簡單... 可是這想法明顯會出人命 因為N個元素就需要有N層for N層for根本沒辦法去描述 而且N層裡面N個指標也宣告不出來orz 如果N固定就沒事了...請教各位要怎麼去做一個普及性的東西呢? ps.補一下"N個元素 挖掉1個空白"的程式碼 http://codepad.org/nhEroSc0 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.64.102.122 ※ 編輯: NitroRider 來自: 61.64.102.122 (05/14 16:32) ※ 編輯: NitroRider 來自: 61.64.102.122 (05/14 16:33)
推
05/14 17:16, , 1F
試試看遞迴?
05/14 17:16, 1F
→
05/14 18:52, , 2F
用遞迴要引入表頭檔嗎@@ 我沒有用過
05/14 18:52, 2F
→
05/14 19:07, , 3F
不用
05/14 19:07, 3F
推
05/14 19:52, , 4F
一共有 2 的 N 次方個這種子集合 每個元素或者拿或者不拿
05/14 19:52, 4F
推
05/14 20:53, , 5F
關鍵字：power set
05/14 20:53, 5F
→
05/14 21:13, , 6F
如果 n <= 64，可以直接用二進位累加的方式
05/14 21:13, 6F
→
05/14 21:14, , 7F
然後判斷每個 bit 決定要不要輸出就好
05/14 21:14, 7F
→
05/14 21:15, , 8F
n > 64 就看要不要用類似的概念這樣
05/14 21:15, 8F
推
05/14 21:18, , 9F
如果要自己實作無限長度的整數只要實作 ++ 和 != 就好
05/14 21:18, 9F
→
05/14 21:21, , 10F
不過 n > 64 非常的多，應該可以考慮限制使用者輸入範圍
05/14 21:21, 10F
→
05/14 21:23, , 11F
遞迴 n 太大感覺會爆，固定 n 編譯時展開也一樣
05/14 21:23, 11F
→
05/14 21:28, , 12F
n超過29~30都要跑很久了..不太可能那麼大吧
05/14 21:28, 12F
→
05/14 21:45, , 13F
對了整數要是 unsigned
05/14 21:45, 13F
→
05/14 22:14, , 14F
power set 的問題比較推薦遞迴解..
05/14 22:14, 14F
→
05/14 23:40, , 15F
所以我這個嘗試有點糟糕嗎...我不知道這會這麼難做@@
05/14 23:40, 15F
→
05/14 23:40, , 16F
我是爬文看到這個東西 想try看看 噗噗
05/14 23:40, 16F
→
05/14 23:54, , 17F
推薦原 PO 先把基礎的東西(語法)看一看再來想這些問題
05/14 23:54, 17F
→
05/14 23:55, , 18F
感覺好像剛學一個禮拜就想越級打怪了XD
05/14 23:55, 18F
推
05/15 02:40, , 19F
我之前好像有分享過排組演算法的實作...
05/15 02:40, 19F
→
05/15 02:41, , 20F
找到了 #1FKF1RAD 參考一下。
05/15 02:41, 20F
→
05/15 11:42, , 21F
只是覺得想難的問題會進步比較快這樣:(
05/15 11:42, 21F
→
05/15 12:32, , 22F
地基沒打好，房子一直蓋
05/15 12:32, 22F
→
05/15 19:25, , 23F
也不用太沮喪拉~其實不會很難
05/15 19:25, 23F
→
05/15 19:27, , 24F
for(unsigned int i=0; i!=(1<<N); cout << endl, ++i)
05/15 19:27, 24F
→
05/15 19:27, , 25F
for(unsigned int j=i, k=1; j; j>>=1, ++k)
05/15 19:27, 25F
→
05/15 19:28, , 26F
if(j&1) cout << k << ",";
05/15 19:28, 26F
→
05/15 19:29, , 27F
思路大概像這樣, 沒仔細check, 你可能要自己 DEBUG 下
05/15 19:29, 27F
→
05/15 19:30, , 28F
不過 1<<N 算是偷懶，如果 N 大於等於 bits 數就不行了
05/15 19:30, 28F
→
05/15 19:30, , 29F
等於要用其他方法給值，大於就只能用更長的unsigned整數
05/15 19:30, 29F
→
05/15 19:32, , 30F
另外抱歉為了要塞到推文~~只好寫短~希望不會造成困擾
05/15 19:32, 30F
→
05/15 19:33, , 31F
只要仔細了解二進位的概念，和右移運算就可以了
05/15 19:33, 31F
→
05/15 20:12, , 32F
對了等於要改成 <=
05/15 20:12, 32F
→
05/15 20:14, , 33F
我是說 n 等於 bit 數要改成 i <= 最大值
05/15 20:14, 33F
→
05/15 21:07, , 34F
我目前寫出來的東西都只到pseudocode的程度 不能用@@
05/15 21:07, 34F
‣ 更多 NitroRider 的文章
文章代碼(AID): #1HaVPmJh (C_and_CPP)