[問題] n個元素的集合

看板C_and_CPP作者 (ZZZZ)時間14年前 (2011/11/22 00:12), 編輯推噓3(3推 0噓 26→)
留言29則, 7人參與, 最新討論串1/2 (看更多)
更正 ========= 原本敘述有點問題 抱歉 我要做的事不只是print 主要是讓那大小為N的陣列內容實際上真的有把2^N種可能跑過一遍 因為我是要用這個陣列去驗證東西 說印出來只是比較好說明而已@@ ========= 一個N個元素的集合 每個元素可以給0或1兩種值 今天我想要把2^n種可能印出來 這n個元素我是用一個一維陣列去放 型態是int 但是是用模擬成二進位的方式印出來 例如N=3的時候 就印000,001,010,011,100,101,110,111 但是想了很久不知道該怎麼寫 請教各位該怎麼寫 還有我覺得用int的一維陣列不是很聰明 感覺應該有別種資料結構可以使用 有什麼更好的選擇嗎? 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.123.215.118
→
11/22 00:16, , 1F
文章代碼(AID): #1EQOZdkZ 是你要的嗎
11/22 00:16, 1F
→
11/22 00:16, , 2F
這個應該在位元運算的章節就有範例可以印了...你所要作的
11/22 00:16, 2F
→
11/22 00:17, , 3F
只有弄個迴圈數字給他加再調整印的範圍...
11/22 00:17, 3F
※ 編輯: death888 來自: 140.123.215.118 (11/22 00:34)
→
11/22 00:53, , 4F
power set ?
11/22 00:53, 4F
→
11/22 00:55, , 5F
用二進位想的確是power set (扣掉空集合)
11/22 00:55, 5F
→
11/22 00:57, , 6F
http://codepad.org/2dD0Ro7p 大概長這樣吧.
11/22 00:57, 6F
→
11/22 00:57, , 7F
不過問題是怎麼讓這個一維陣列模擬成二進位真的從
11/22 00:57, 7F
→
11/22 00:57, , 8F
000...000跑到111...111呢
11/22 00:57, 8F
→
11/22 00:59, , 9F
你的問題點是,不想用bitwise,還是怕元素超過64個?
11/22 00:59, 9F
→
11/22 01:01, , 10F
因單純用 array 模擬 2 進位變化來做 power set,低效.
11/22 01:01, 10F
→
11/22 01:08, , 11F
用bitwise做得到我要的效果嗎@@? 實際上我的元素會上千個
11/22 01:08, 11F
→
11/22 01:13, , 12F
這種東西通常都用bitwise 來作阿
11/22 01:13, 12F
→
11/22 01:14, , 13F
arr[i/32]>>(i%32)&0x1, 64 bit環境就把32換64
11/22 01:14, 13F
推
11/22 01:15, , 14F
bitwise也可以跨陣列去做,重點就變成 1000 會落在第
11/22 01:15, 14F
→
11/22 01:15, , 15F
上千上萬都不是啥問題阿
11/22 01:15, 15F
→
11/22 01:15, , 16F
1000/32陣列,第1000%32元素裡面.(推慢了,a大給的是通)
11/22 01:15, 16F
→
11/22 01:17, , 17F
而用你的想法其實很簡單完成,只要實作完 X 進制的大數
11/22 01:17, 17F
→
11/22 01:17, , 18F
演算法,答案就出來了. http://codepad.org/7UMcmh5b
11/22 01:17, 18F
→
11/22 01:17, , 19F
但它真的是低效。
11/22 01:17, 19F
→
11/22 01:28, , 20F
感謝a大t大 那除了用array模擬 有其他較好的方法嗎?
11/22 01:28, 20F
→
11/22 01:31, , 21F
有,目前看過最高效 (唯一 codepad 沒跑到當的) 的演算
11/22 01:31, 21F
→
11/22 01:31, , 22F
法在 TAOCP Vol4, 我也看不懂,只是照 pseudo code 編
11/22 01:31, 22F
→
11/22 01:32, , 23F
http://codepad.org/812zGijk ,看懂的人麻煩解釋一下
11/22 01:32, 23F
→
11/22 01:39, , 24F
另不知道是什麼原因要窮舉所有子集合?光64bits要窮舉完
11/22 01:39, 24F
→
11/22 01:40, , 25F
就要費很多時間,建議先確認你的方向是不是正確。
11/22 01:40, 25F
推
11/22 04:45, , 26F
看問題的大小, 適當地用窮舉方法.
11/22 04:45, 26F
→
11/22 04:45, , 27F
除非你有超級的超級電腦.
11/22 04:45, 27F
→
11/22 14:48, , 28F
自首一件事..我記錯了,那份code是給 perm. 用的 XD.
11/22 14:48, 28F
推
11/23 14:24, , 29F
branch 用stack(or queue)就可以做出來了
11/23 14:24, 29F
‣ 更多 death888 的文章
文章代碼(AID): #1EodXuYi (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 death888 的文章
文章代碼(AID): #1EodXuYi (C_and_CPP)