作业帮 > 综合 > 作业

列举一个n元集合的所有子集的思路

来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/10/05 01:56:45
列举一个n元集合的所有子集的思路
要求用java实现列举一个n元集合的所有子集,一点头绪也没有,小妹拜谢!
你试试能不能用~
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class FindSubset {
private BitSet start;
private BitSet end;
private Set subsets;
public FindSubset() {
this.start = new BitSet();
this.end = new BitSet();
this.subsets = new HashSet();
}
public void execute(int n, Set items) {
int size = items.size();
for (int i = 0; i < n; i++) {
start.set(i, true);
}
for (int i = n; i < size; i++) {
start.set(i, false);
}
for (int i = size - 1; i > size - n; i--) {
end.set(i, true);
}
for (int i = 0; i < size - n; i++) {
end.set(i, false);
}
find(items);
while (start != end) {
boolean endBit = start.get(size - 1);
int last10 = -1;
int i;
for (i = size - 1; i > 0; i--) {
boolean former = start.get(i - 1);
boolean last = start.get(i);
if (former == true && last == false) {
last10 = i - 1;
break;
}
}
if (i == 0) {
break;
} else {
if (endBit == false) {
start.set(last10, false);
start.set(last10 + 1, true);
find(items);
} else {
start.set(last10, false);
start.set(last10 + 1, true);
last10 += 1;
for (int j = last10 + 1; j < size; j++) {
if (start.get(j)) {
start.set(j, false);
start.set(last10 + 1, true);
last10 += 1;
find(items);
}
}
}
}
}
}
public void find(Set items) {
Set temp = new HashSet();
Object elements[] = items.toArray();
for (int i = 0; i < elements.length; i++) {
if (start.get(i)) {
temp.add(elements[i]);
}
}
subsets.add(temp);
}
public Set getSubsets() {
return this.subsets;
}

public void clearSubsets(){
this.subsets.clear();
}
public static void main(String[] args) {
Set items = new HashSet();
items.add("A");
items.add("B");
items.add("C");
items.add("D");
items.add("E");
items.add("F");
FindSubset fs = new FindSubset();
for (int i = 0; i < items.size(); i++) {
System.out.println((i + 1) + "元子集:");
fs.execute(i + 1, items);
Iterator iterator = fs.getSubsets().iterator();
while (iterator.hasNext()) {
Object[] subset = iterator.next().toArray();
System.out.print("{");
for (int j = 0; j < subset.length - 1; j++) {
System.out.print(subset[j] + ",");
}
System.out.print(subset[subset.length - 1]);
System.out.println("}");
}

fs.clearSubsets();
}
}
}