CODEWITHSUNDEEP
javaalgorithmcombinations
pasq
pasq

Reputation: 1

Algorithm for combination

I have designed an algorithm in java I generate all combinations of elements of a list . For example whereas the elements [A, B , C] it generates combinations , [A] , [B] , [C] , [AB] , [BC] , [ABC] . Or based on the elements [A, A, B] generates combinations [A] , [B] , [AA] , [AB] , [AAB] . This is my code to generate combinations .

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

    }

But however for input > 250 the program stops and takes too long to make all combinations . How can I improve this solution ? Or is there a better solution ?

Upvotes: 1

Views: 124

Answers (2)

NiVeR
NiVeR

Reputation: 9786

This is the basic idea that I was telling you. I am inserting only the few key points. You should attach this to your code as you know best.

  public void findnThCombination(List<Elemento> combinazioni, int n) {
    ...
    int counter_combinations = 0; 
    // 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));
    }
    counter_combinations ++;
    // do bfs until we have no elements
    while(!queue.isEmpty()) {
         //when you add a new combination
         counter_combinations++;
         if(counter_combinations == n) //return this combination
    }}

I hope this helps.

Upvotes: 1

maskacovnik
maskacovnik

Reputation: 3084

For input=250, there will be so much combinations: Look at this example:

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

as you can see, there will be 2^n-1 elements

So for input=250 - 2^250-1 = large number (1.8*10^75)

Too much memory is used. I think number about 20 (1048575) will make trouble too

Upvotes: 3

Related Questions