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

Note power sets get large quickly, so this will run out of memory for even fairly small inputs. However if you have the memory, there are no other restrictions.

// 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 に答える
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 に答える