如何从arrayList对象中创建所有可能的幂集（或子集）？

说我有以下课程：

class A { String name; Double value; } 

以及可能具有以下内容的上述类对象的列表：

 [{f 2.1}, {c 1.1}, {a 0.3}... and so on] [{n 0.5}, {f 1.9}, {x 0.1}, {a 1.9}, {b 1.1}... and so on] ... and so on 

我想要的只是做以下事情：

 1. Building power subsets from the internal list items(NB: skip the single subsets). 2. Push the subset in another List as an object of the above class A like this: a. if f,c is a subset of 1st element then f,c would be the name property of class A and the value property will be the minimum of f and c from the list. Like: {f,c 1.1} [ where f,c is a subset and min of 2.1(value of f) and 1.1(value of c) is 1.1] so, from the above list if I take 1st element the subsets and their values in the pushing list would be like this(after skipping the single subsets): [{f,c 1.1}, {c,a 0.3}, {f,a 0.3}, {f,c,a 0.3}] and for the 2nd element this would be: [{n,f 0.5}, {f,x 0.1}, {x,a 0.1}, {a,b 1.1}, {n,x 0.1}, {n,a 0.5}, {n,b 0.5}, {f,a 1.9}, {f,b 1.1}, {x,b 0.1}, {n,f,x 0.1}, {n,x,a 0.1}, {n,a,b 0.5}, {f,x,a 0.1}, {f,x,b 0.1}, {x,a,b 0.1}, {n,f,x,a 0.1}, {n,f,x,b 0.1}, {n,f,a,b 0.5}, {n,x,a,b 0.1}, {f,x,a,b 0.1}, {n,f,x,a,b 0.1}] 

任何人都可以建议我，我怎么能用Java做这个（如果可能的话，有一些示例代码）。

谢谢！

Answer 1

注意电源设置会很快变大，因此即使是相当小的输入也会耗尽内存。 但是，如果你有内存，则没有其他限制。

 // As stated. class A { String name; double value; A(String name, double value) { this.name = name; this.value = value; } } // Powerset set. class ASet { final ArrayList names = new ArrayList(); double value = Double.MAX_VALUE; void adjoin(A a) { names.add(a.name); value = Math.min(value, a.value); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('{'); for (String name : names) { sb.append(name); sb.append(','); } sb.append(value); sb.append('}'); return sb.toString(); } } // Make power sets. class PowerSetFactory { // Stack for intermediate results. final ArrayDeque stack = new ArrayDeque(); // Source data. ArrayList src; // Powerset under construction ArrayList dst; // Recursive powerset calculator private void recur(int i) { if (i >= src.size()) { // Stack is complete. If more than 1 element, // add its contents to the result. if (stack.size() > 1) { ASet set = new ASet(); for (A a : stack) set.adjoin(a); dst.add(set); } } else { // Otherwise recur both without and with this element // added to the stack. Clean up the stack before return. recur(i + 1); stack.offerLast(src.get(i)); recur(i + 1); stack.pollLast(); } } // Get a powerset for the givens source data. ArrayList getPowerSet(ArrayList src) { this.src = src; this.dst = new ArrayList(); recur(0); return dst; } public void test() { ArrayList data = new ArrayList(); data.add(new A("f", 2.1)); data.add(new A("c", 1.1)); data.add(new A("a", 0.3)); for (ASet set : getPowerSet(data)) { System.out.print(set); } System.out.println(); data.clear(); data.add(new A("n", 0.5)); data.add(new A("f", 1.9)); data.add(new A("x", 0.1)); data.add(new A("a", 1.9)); data.add(new A("b", 1.1)); for (ASet set : getPowerSet(data)) { System.out.print(set); } System.out.println(); } } 

Answer 2

我假设输出列表的每个元素上的子集的顺序是无关紧要的。

对于任何大小的输入，您的输出将是难以处理的大，所以不要试图将其保留在内存中。 您最好将PowerList实现为自己的集合。 以下草案仅适用于长度为31或更短的输入，并且不会过滤单例或空列表。

 public class PowerList extends AbstractList< A > { private final List< A > laUnderlying; public PowerList( List< A > laUnderlying ) { this.laUnderlying = laUnderlying; } @Override public A get( int index ) { StringBuilder sbLabel; A aOut = new A(); aOut.value = Double.MAX_VALUE; int iUnderIndex = 0; while ( 0 < index ) { while ( 0 == ( index & 1 ) ) { ++iUnderIndex; index = index >> 1; } A aComponent = laUnderlying.get( index ); sbLabel.append( ',' ).append( aComponent.name ); if ( aComponent.value < aOut.value ) aOut.value = aComponent.value; } if ( !sbLabel.isEmpty() ) aOut.name = sbLabel.substring( 1 ); return aOut; } public int size() { return 1 << laUnderlying.size(); } } 

现在你原来的问题减少到了

 List< List< A > > llaOutput; for ( List< A > laEach : llaInput ) llaOutput.add( new PowerList( laEach ) );