如何使所有可能的功率集（或子集）从arrayList对象？ [英] how to make all possible power set(or subset) from arrayList objects?

问题描述

说我有以下类：

class A {
    String name;
    Double value;
}

以及上述类对象的列表，可能包含：

and a list of the above class objects which might have:

[{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

我想要的是执行以下操作：

all I want is to do the followings:

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示例代码）。

Can anybody suggest me please how can I do this in Java(with some sample code if possible).

感谢！

推荐答案

集合很快就会变大，因此即使是相当小的输入也会耗尽内存。但是，如果你有内存，没有其他限制。

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();
    }
}

这篇关于如何使所有可能的功率集（或子集）从arrayList对象？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！