Re: [緊急]請問一下求子集合

看板java作者TonyQ (骨頭)時間19年前 (2006/03/15 15:15)推噓2(2推 0噓 0→)

留言2則, 1人參與討論串1/1

※ 引述《ardidi.bbs@bbs.wretch.cc (在抉擇的十字路)》之銘言： : ※ 引述《ardidi (在抉擇的十字路)》之銘言： : 算了...這由我自己來解答好了 : 看的懂的就看吧 : 不過沒有印出空集合 : public class set{ : public static void main(String[] args){ : int[] tmp1=new int[這裡改成tmp陣列裡的個數]; : int[] tmp={1,2,3,5};//<---這裡自己改 : System.out.println("{}"); : set.work(tmp,0,tmp1,0); : } : public static void work(int[] tmp,int a,int[] tmp1,int b){ : while(a>=0){ : int c=0; : if(a-1>=0){ : c=a-1; : } : if(tmp1[c]==tmp[tmp.length-1]){ : set.work(tmp,a-2,tmp1,1); : }else{ : if(b==1){ : for(int i=0;i<tmp.length;i++){ : if(tmp1[a]==tmp[i]){ : tmp1[a]=tmp[i+1]; : break; : } : } : }else{ : if(a-1<0){ : tmp1[a]=tmp[0]; : }else{ : for(int i=0;i<tmp.length;i++){ : if(tmp[i]==tmp1[a-1]){ : tmp1[a]=tmp[i+1]; : break; : } : } : } : } : String str=""; : for(int i=0;i<a;i++){ : str+=tmp1[i]+","; : } : System.out.println("{"+str+tmp1[a]+"}"); : set.work(tmp,a+1,tmp1,0); : } : } : } : } 這問題剛好是我們最近的作業，(當然是已經交出去的作業XD) 收到的題目是將一個Set所有的子集合包括空集合都列出。(power_set問題) 我想了兩個方式，一個是iterator 利用2進位的方式輸出，另一個是recursive，其實也是差不多的概念。XD 改成object是故意的，不過好像有點繁瑣～:P 不過板上沒有類似的文章，所以來貼一下，看看有沒有人想討論的... Iterator版 static void power_set_iter(Object[] InputData){ boolean[] check=new boolean[InputData.length]; for(int back=InputData.length-1;back!=-1;){ for(int i=0;i<InputData.length;i++){ if(check[i]) System.out.print( InputData[i]); } System.out.println(); for(back=InputData.length-1;back>=0&&check[back];back--){ check[back]=false; } if(back!=-1) check[back]=true; } } Recursive版 static void power_set(String step,Object[] input,int n) { if(n==input.length) System.out.println(step); else{ power_set(step+input[n],input,n+1); power_set(step,input,n+1); } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.138.240.58