java - 组合算法

Question

我在 java 中设计了一个算法，我生成一个列表元素的所有组合。例如，元素 [A, B, C] 它生成组合，[A]，[B]，[C ] , [AB] , [BC] , [ABC] 。或者根据元素 [A, A, B] 生成组合 [A] , [B] , [AA] , [AB] , [AAB] 。这是我生成组合的代码。

private List<Elemento> combinazioneMassima = new ArrayList<>();
    private Log logger = LogFactory.getLog(Combinazioni3.class);

    public Combinazioni3(List<Elemento> generaCombinazioneMassima) {
        this.combinazioneMassima = generaCombinazioneMassima;
    }

    public void combine() {
        this.findAllCombinations(combinazioneMassima);
    }

    private static class Node{
        int lastIndex = 0;
    List<Elemento> currentList;
    public Node(int lastIndex, List<Elemento> list) {
            this.lastIndex = lastIndex;
            this.currentList = list;
    }
    public Node(Node n) {
            this.lastIndex = n.lastIndex;
            this.currentList = new ArrayList<Elemento>(n.currentList);
    }
    }

    public void findAllCombinations(List<Elemento> combinazioni) {
        Date dataInizio = new Date();
        List<List<Elemento>> resultList = new ArrayList<List<Elemento>>();
        LinkedList<Node> queue = new LinkedList<Node>();
        int n = combinazioni.size();
        ArrayList<Elemento> temp = new ArrayList<Elemento>();
        temp.add(combinazioni.get(0));
        queue.add(new Node(0, temp));
        // add all different integers to the queue once.
        for(int i=1;i<n;++i) {
                if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
                temp = new ArrayList<Elemento>();
                temp.add(combinazioni.get(i));
                queue.add(new Node(i, temp));
        }
        // do bfs until we have no elements
        while(!queue.isEmpty()) {
                Node node = queue.remove();
                if(node.lastIndex+1 < n) {
                        Node newNode = new Node(node);
                        newNode.lastIndex = node.lastIndex+1;
                        newNode.currentList.add(combinazioni.get(node.lastIndex+1));
                        queue.add(newNode);
                }
                for(int i=node.lastIndex+2;i<n;++i) {
                        if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
                        // create a copy and add extra integer
                        Node newNode = new Node(node);
                        newNode.lastIndex = i;
                        newNode.currentList.add(combinazioni.get(i));
                        queue.add(newNode);
                }
                GestoreRegole gestoreRegole = new GestoreRegole();
                gestoreRegole.esegui(node.currentList);
        }

    }

但是对于 input > 250 程序停止并且需要很长时间才能完成所有组合。我怎样才能改进这个解决方案？或者有更好的解决方案吗？

Answer 1

对于input=250，会有这么多的组合:看这个例子:

(1) {a}     => {a}
(3) {a,b}   => {a}, {b}, {a,b}
(7) {a,b,c} => {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}

如你所见，会有2^n-1个元素

因此对于输入=250 - 2^250-1 = large number (1.8*10^75)

使用了过多的内存。我觉得20号左右(1048575)也会出事