MyException - 我的异常网
当前位置:我的异常网» J2SE » 高手帮小弟我解读一下这个求幂集的程序,多谢

高手帮小弟我解读一下这个求幂集的程序,多谢

www.MyException.Cn  网友分享于:2013-12-11  浏览:49次
高手帮我解读一下这个求幂集的程序,谢谢
算法目的就是求一个集合的幂集,比如:集合A={a,b,c},则A的幂集p(A)={a,b,c,ab,ac,bc,abc,空}
从网上找到了这个算法,可我看了一晚上也没看懂后面递归是什么意思,不知道求幂集的算法思想,谁能帮小弟看一看,给我讲一下算法思想,谢谢

import java.util.*;

public class Collection {

public static void main(String[] args) {
Vector collection = new Vector();

collection.add("a");
collection.add("b");
collection.add("c");

Object[] o = function (collection);

for (int i = 0 ; i < o.length ; i++ ){
List a = (List)o[i];
if(a.size() > 0) {
System.out.println(a);
}
}
}

public static Object[] function(Vector collection) {

ArrayList pCollection = new ArrayList();
ArrayList collectionTemp = new ArrayList();

function1 (1, collection, collectionTemp, pCollection);

Object[] o = pCollection.toArray();

return o;

}
   
public static void function1(int i, Vector collection, ArrayList collectionTemp, ArrayList pCollection) {

if (i > collection.size()){
pCollection.add(collectionTemp.clone());
} else {

Object o = collection.elementAt(i-1);  
collectionTemp.add(o);  
function1(i+1,collection,collectionTemp,pCollection); //就这3条递归语句看不明白,我觉得关键是没有理解该算法的思想
collectionTemp.remove(collectionTemp.size()-1);  
function1(i+1,collection,collectionTemp,pCollection);
}
}
}


------解决方案--------------------
求幂积最简单的算法思想就是从最后一个元素倒着来遍历所有元素,比如说最后一个就是自己 "c" ;
倒数第二个:首先把自己和幂积里面已有的所有元素做乘积("bc"),然后加到幂积里,此时为{c,bc};最后再加上自己"b",{b,c,bc}
倒数第三个:把自己(a)和幂积中所有元素做乘积{ab,ac,abc},加到幂积集合中,此时幂积中为:{b,c,bc,ab,ac,abc};最后再加上自己本身"a",为:{a,b,c,bc,ab,ac,abc}.
依次类推即可,多少元素都能计算其幂积,至于具体编程就不说了,有这个思想,编程应该是比较简单了,就留给楼主了。
------解决方案--------------------
无非就是一个递归嘛 看下面这个函数我们可以知道最终的结果是存在了一个Object数组中 
Java code
public static Object[] function(Vector collection) { 

ArrayList pCollection = new ArrayList(); 
ArrayList collectionTemp = new ArrayList(); 

function1 (1, collection, collectionTemp, pCollection); 

Object[] o = pCollection.toArray(); //Object数组的值来自于ArrayList pCollection,也就是说collectionTemp是过渡的  

return o; 

}

------解决方案--------------------
用二进制数的原理自己写一个也很简单.
------解决方案--------------------
呵呵,一开始我也看不明白,在本地运行了一下,结果是:
[a, b, c]
[a, b]
[a, c]
[a]
[b, c]
[b]
[c]
理解递归并不难,我觉得比较难想到的是处理后面的逻辑
collectionTemp.remove(collectionTemp.size()-1);
function1(i+1,collection,collectionTemp,pCollection);

删除集合的最后一个元素再调用递归, 这个才是这个算法的关键.

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有