Get all possible combinations (power set) from ArrayList (or set) of elements

Question

I have a class Product where a product has a name:

package main;

public class Product {

    private String name;

    public Product(String name) {
        super();
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

}

And a class Combination where a combination has an array list of products:

package main;

import java.util.ArrayList;

public class Combination {

    private ArrayList<Product> products;

    public Combination(ArrayList<Product> products) {
        super();
        this.products = products;
    }

    public ArrayList<Product> getProducts() {
        return products;
    }

    public void setProducts(ArrayList<Product> products) {
        this.products = products;
    }   

}

In Main I create an array list of products and I want to get all possible combinations of products.

package main;

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        ArrayList<Product> products = new ArrayList<Product>();

        products.add(new Product("p1"));
        products.add(new Product("p2"));
        products.add(new Product("p3"));
        products.add(new Product("p4"));

        ArrayList<Combination> combinations = getCombinations(products);

    }

    public static ArrayList<Combination> getCombinations(ArrayList<Product> products){
        ArrayList<Combination> combinations = new ArrayList<Combination>();
        //CODE TO ADD
        return combinations;
    }

}

What is the fastest solution to get all combinations? In the shown example I will get the following combinations:

p1

p1 p2

p1 p2 p3

p1 p2 p3 p4

p1 p2 p4

p1 p3

p1 p3 p4

p1 p4

p2

p2 p3

p2 p3 p4

p2 p4

p3

p3 p4

p4

I don't care about the order in which I retrieve the combinations, the important is to get all of them in the fastest way.

this might be helpful [Calculate all possible combinations of given characters](https://codereview.stackexchange.com/questions/41510/calculate-all-possible-combinations-of-given-characters) — matoni, Jul 17 '17 at 17:07
See permutation of an array here at SO: https://stackoverflow.com/questions/2920315/permutation-of-array — deHaar, Jul 17 '17 at 17:17
This is a duplicate. Besides, you should show some effort to get a solution, then ask about any problem you experience. — fps, Jul 17 '17 at 18:14

score 0 · Accepted Answer · answered Jul 18 '17 at 06:31

To get all possible combinations, I use the PowerSet method provided by guava: google core libraries for java

First, I use a maven project where I add the guava dependency to the pom.xml:

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>22.0</version>
</dependency>

Then I added the content of the getCombinations method and I printed the result in the main method:

package main;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import com.google.common.collect.Sets;

public class Main {

    public static void main(String[] args) {

        ArrayList<Product> products = new ArrayList<Product>();

        products.add(new Product("p1"));
        products.add(new Product("p2"));
        products.add(new Product("p3"));
        products.add(new Product("p4"));

        ArrayList<Combination> combinations = getCombinations(products);

        for (Combination combination : combinations) {
            for (Product product : combination.getProducts()) {
                System.out.print(product.getName() + " ");
            }
            System.out.println();
        }

    }

    public static ArrayList<Combination> getCombinations(ArrayList<Product> products) {
        ArrayList<Combination> combinations = new ArrayList<Combination>();
        Set<Product> productsSet = new HashSet<Product>(products);
        Set<Set<Product>> combinationsSet = Sets.powerSet(productsSet);
        Iterator<Set<Product>> combinationsIterator = combinationsSet.iterator();
        while (combinationsIterator.hasNext()) {
            ArrayList<Product> productsList = new ArrayList<Product>(combinationsIterator.next());
            Combination combination = new Combination(productsList);
            combinations.add(combination);
        }
        return combinations;
    }
}

Output:

p1

p4

p1 p4

p3

p1 p3

p4 p3

p1 p4 p3

p2

p1 p2

p4 p2

p1 p4 p2

p3 p2

p1 p3 p2

p4 p3 p2

p1 p4 p3 p2

Since I don't care about order, the obtained result is fine for me. Note that the PowerSet method is applied on Sets so I had to convert ArrayList to Set to use it.

Get all possible combinations (power set) from ArrayList (or set) of elements

1 Answers1