求助 求幂集

Question

public static Vector getPowers( Vector a ) {
   Vector ret = new Vector() ; 
   
   String one = "" ;    if ( a.length() == 0 ) return ret ; 
   
   //求全集 [a] [b] [c] [d] 返回 [abcd]     
   for ( int i = 0 ; i < a.length() ; i ++ ) {
     string s = (string) a.get( i ) ;  
     one += s ; 
   }
   ret.add( one ) ;   //减少一个元素调用getPowers重新在求全集
   for ( int i = 0 ; i < a.length() ; i ++ ) {
       Vector b = a.clone() ; 
       b.remove( i ) ; 
       Vector last = getPower( b ) ; 
       ret.addAll( last ) ; 
   }   return ret ; 
}

Answer 1

tyrone98(林林) 所写的没有对元素进行排序
这样的输出有很多元素的
而且就单单求幂集的结果就不对的
不过还是十分感谢为我思考

Answer 2

用递归实现较简单(此程序未优化)import java.util.*;public class Test {
  public static void main(String[] args) {
Vector v= new Vector();
v.add("a");v.add("b");v.add("c");v.add("d");
Object[] o = ff(v);
for(int i=0;i<o.length;i++){
ArrayList a = (ArrayList)o[i];
if(a.size()>0)System.out.println(a);
}
  }
  
  public static Object[] ff(Vector v){
   ArrayList set = new ArrayList(),
   result = new ArrayList();
   ff1(1,v,set,result);
   Object o[] = result.toArray();  
   Arrays.sort(o,new Comparator(){
   public int compare(Object o1,Object o2){
   int a = ((ArrayList)o1).size(),
       b = ((ArrayList)o2).size();
   return a-b;
   }
   });  
   return o;  
  }
  
  private static  void ff1(int i,Vector v,ArrayList set,ArrayList result){
   if(i>v.size())result.add(set.clone());
   else{
   Object o = v.elementAt(i-1);
   int count = set.size();
   set.add(o);
   ff1(i+1,v,set,result);
   set.remove(set.size()-1);
   ff1(i+1,v,set,result);
   }  
  }
}

Answer 3

我写错了，现在不用递归，你可以试试,不好意思了
public static Vector getPowers( Vector a ) {
   Vector ret = new Vector() ; 
   
   String one = "" ;     if ( a.size() == 0 ) return ret ; 
   
   for ( int cnt = 1 ; cnt <= a.size() ; cnt ++  ) {
    ret.addAll( getPowers( a , cnt) ) ;
   
   }    return ret ; 
}
private static Vector getPowers ( Vector a , int cnt ) {
Vector ret = new Vector()  ; 
int pos[] = new int[cnt] ;

for ( int i = 0 ; i < pos.length ; i ++ ) {
pos[i] = i ; 
}

int posMoved = cnt - 1 ; 

while ( true ) {
if ( posMoved == -1 )
break ; 

ret.add( getItem(  a , pos ) ) ;

pos[posMoved] ++ ;
 
//进位
if ( pos[posMoved] == ( a.size() - ( cnt - posMoved ) + 1 ) ) {
for ( ; posMoved >= 0 ; posMoved -- ) {
if ( pos[posMoved] < ( a.size() - ( cnt - posMoved )  ) ) {
break ;
}
}

if ( posMoved >= 0 ) {
pos[posMoved] ++ ;

for ( int j = 1 ; j < cnt - posMoved  ; j ++ ) {
pos[posMoved + j] = pos[posMoved] + j ;
}

posMoved = cnt - 1 ;
}
}
}
 

return ret ; 
}

private static String getItem( Vector a , int[] pos ) {
String ret = "" ;

for ( int i = 0 ; i < pos.length ; i ++ ) {
ret = ret + (String) a.get( pos[i] ) ;  
}

return ret ; 
}

public static void main( String[] args  ) {
Vector b = new Vector() ; 
b.add( "A") ;
b.add( "B") ;
b.add( "C") ;
b.add( "D") ;
b.add( "E") ;
b.add( "F") ;

Vector ret = getPowers( b ) ;

System.out.println( "hello every one") ;
Iterator iter = ret.iterator() ;

while( iter.hasNext() ) {
System.out.println( "item="+ iter.next() ) ;
}
}

Answer 4

强啊
 tyrone98(林林)  
我试过了
很对
谢谢你了

Answer 5

把我的if(a.size()>0)去掉放空集出来

Answer 6

to:tyrone98(林林) 用下面方法测试一下我俩算法时间效率
   for(int i=0;i<15;i++){
  
   System.out.println(i);
Vector v= new Vector();
for(int j=0;j<i;j++)
v.add(String.valueOf(j));

long l1=System.currentTimeMillis();
Object[] o = ff(v);
long l2=System.currentTimeMillis();
System.out.println("ntzls used:"+(l2-l1));

l1=System.currentTimeMillis();
Vector ret = getPowers(v) ;
l2=System.currentTimeMillis();
System.out.println("tyrone98 used:"+(l2-l1));

System.out.println("----------------------------------------------");
}
参考数据：
0
ntzls used:0
tyrone98 used:0
----------------------------------------------
1
ntzls used:0
tyrone98 used:0
----------------------------------------------
2
ntzls used:0
tyrone98 used:0
----------------------------------------------
3
ntzls used:0
tyrone98 used:0
----------------------------------------------
4
ntzls used:0
tyrone98 used:0
----------------------------------------------
5
ntzls used:0
tyrone98 used:0
----------------------------------------------
6
ntzls used:0
tyrone98 used:0
----------------------------------------------
7
ntzls used:0
tyrone98 used:10
----------------------------------------------
8
ntzls used:10
tyrone98 used:10
----------------------------------------------
9
ntzls used:10
tyrone98 used:10
----------------------------------------------
10
ntzls used:10
tyrone98 used:10
----------------------------------------------
11
ntzls used:0
tyrone98 used:20
----------------------------------------------
12
ntzls used:10
tyrone98 used:50
----------------------------------------------
13
ntzls used:30
tyrone98 used:130
----------------------------------------------
14
ntzls used:101
tyrone98 used:330
----------------------------------------------非递归算法应能胜过递归算法的，呵呵

Answer 7

呵呵，是吗，我想可能是由于我做了
private static String getItem( Vector a , int[] pos ) {
String ret = "" ;

for ( int i = 0 ; i < pos.length ; i ++ ) {
ret = ret + (String) a.get( pos[i] ) ;  
}

return ret ; 
}
把字符串粘起来的原由吧，而且ArrayList应当比Vector效率要高吧。改完为我们的差别是
0
ntzls used:0
tyrone98 used:0
----------------------------------------------
1
ntzls used:0
tyrone98 used:0
----------------------------------------------
2
ntzls used:0
tyrone98 used:0
----------------------------------------------
3
ntzls used:0
tyrone98 used:0
----------------------------------------------
4
ntzls used:0
tyrone98 used:0
----------------------------------------------
5
ntzls used:0
tyrone98 used:0
----------------------------------------------
6
ntzls used:0
tyrone98 used:0
----------------------------------------------
7
ntzls used:10
tyrone98 used:0
----------------------------------------------
8
ntzls used:0
tyrone98 used:0
----------------------------------------------
9
ntzls used:10
tyrone98 used:0
----------------------------------------------
10
ntzls used:0
tyrone98 used:0
----------------------------------------------
11
ntzls used:0
tyrone98 used:0
----------------------------------------------
12
ntzls used:10
tyrone98 used:10
----------------------------------------------
13
ntzls used:20
tyrone98 used:10
----------------------------------------------
14
ntzls used:70
tyrone98 used:50
----------------------------------------------
15
ntzls used:130
tyrone98 used:100
----------------------------------------------
16
ntzls used:281
tyrone98 used:180
----------------------------------------------
呵呵，好象我的计算机比你快

Answer 8

改成这样
public static ArrayList getPowers( Vector a ) {
   ArrayList ret = new ArrayList() ; 
   
   if ( a.size() == 0 ) return ret ; 
   
   for ( int cnt = 1 ; cnt <= a.size() ; cnt ++  ) {
    getPowers( a , cnt , ret) ;
   
   }    return ret ; 
}
private static void getPowers ( Vector a , int cnt , ArrayList ret ) {
int pos[] = new int[cnt] ;

for ( int i = 0 ; i < pos.length ; i ++ ) {
pos[i] = i ; 
}

int posMoved = cnt - 1 ; 

while ( true ) {

ret.add( getItem(  a , pos , cnt ) ) ;

pos[posMoved] ++ ;
 
//进位
if ( pos[posMoved] == ( a.size() - ( cnt - posMoved ) + 1 ) ) {
for ( ; posMoved >= 0 ; posMoved -- ) {
if ( pos[posMoved] < ( a.size() - ( cnt - posMoved )  ) ) {
break ;
}
}

if ( posMoved >= 0 ) {
pos[posMoved] ++ ;

for ( int j = 1 ; j < cnt - posMoved  ; j ++ ) {
pos[posMoved + j] = pos[posMoved] + j ;
}

posMoved = cnt - 1 ;
}

if ( posMoved == -1 )
break ; 

}
}
}

private static String[] getItem( Vector a , int[] pos , int cnt ) {
String[] ret = new String[cnt] ;

for ( int i = 0 ; i < pos.length ; i ++ ) {
ret[i] = (String)a.get(i) ;
}

return ret ; 
}