1

假设我有以下课程：

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(N.B: 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中做到这一点（如果可能的话，使用一些示例代码）。

谢谢！

4

2 回答 2

1

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

对于任何显着大小的输入，您的输出将非常大，因此不要尝试将其保存在内存中。您最好将 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 ) );
于 2012-06-13T19:50:02.277 回答
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<String> names = new ArrayList<String>();
    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<A> stack = new ArrayDeque<A>();

    // Source data.
    ArrayList<A> src;

    // Powerset under construction
    ArrayList<ASet> 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<ASet> getPowerSet(ArrayList<A> src) {
        this.src = src;
        this.dst = new ArrayList<ASet>();
        recur(0);
        return dst;
    }

    public void test() {
        ArrayList<A> data = new ArrayList<A>();
        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();
    }
}
于 2012-06-13T20:29:43.907 回答