Java - Permutation of objects in Arraylist within an Arraylist

Question

I am new to Java and Stack Overflow and I have a question about permutation.

Method: I generate ArrayList with objects within an ArrayList. Each ArrayList has the size from 1 (minium 1 possible) to infinite and contains custom generated objects with an unique name-attribute.

Question: Now my question is how i can get the permutation of all possible combinations of objects from the first ArrayList to the lastArrayList (i guess we can say that's the x-axis) within my outer ArrayList (y-axis)?

Example: I try to draw a simple example:

1. ArrayList: 1.1 | 1.2 | 1.3
2. ArrayList: 2.1
3. ArrayList: 3.1 | 3.2

Here these ArrayLists are in the outer ArrayList (because of the unknown number of possible ArrayLists with objects). And the second number is to show the different objects. Let's say "get every possible combination to get from top to bottom".

Result: I want to get a result which looks like this:

1. Combination: 1.1 | 2.1 | 3.1
2. Combination: 1.1 | 2.1 | 3.2
3. Combination: 1.2 | 2.1 | 3.1
4. Combination: 1.2 | 2.1 | 3.2
5. Combination: 1.3 | 2.1 | 3.1
6. Combination: 1.3 | 2.1 | 3.2

Edit: Here the separator "|" stands for e.g. a slot in an ArrayList. The combinations shouldn't be writen in the console because i need to access every object of the permutation individually.

The best case would be if I can get each combination after the other because I want to check several conditions on each combination and only safe certain combinations in a further ArrayList or an .txt-file.

What i got so far: I have found a code snippet which permutates ArrayLists with Strings within an ArrayList and returns a single ArrayList with the combined Strings.

public static ArrayList<String> combineAllCases(ArrayList<ArrayList<String>> totalList)
{
ArrayList<String> result = new ArrayList<String>(totalList.get(0));

    for(int index = 1; index < totalList.size() ; index++)
    {
        result = (ArrayList<String>) combineTwoLists(result, totalList.get(index));
    }
    return result;
}

and

    private static ArrayList<String> combineTwoLists(ArrayList<String> list1, ArrayList<String>   list2)
{
ArrayList<String> result = new ArrayList<String>();
    StringBuilder sb = new StringBuilder();
    for(String s1 : list1)
    {
        for(String s2: list2)
        {
            sb.setLength(0);
            sb.append(s1).append("#").append(s2);
            result.add(sb.toString());
        }
    }
    return result;
}

The idea: With this method, I could use a String split to get each object name per combination and could search for this name the old ArrayLists to get the object back.

The problem: This method works only for a small number of ArrayLists within an ArrayList (e.g. like the example above). If a have e.g. 16 ArrayLists of the size of 7 in the outer ArrayList, I get an Error of "MemoryOutOfSpace".

So as mentioned the best case would be to get combination after combination and decide individually if I want to keep the combination or not (I guess I would save each combination in a .txt-file because it could be, that I want to keep every combination --> bypass the problem of a further "MemoryOutOfSpace"-Error).

Short summary: Inner-ArrayLists with objects (size from 1 to unknown size). Outer-ArrayList with the inner-ArrayLists (unknown size). Wanted Output: every combination of objects from top to bottom.

Thanks in advance.

Answer 1

//Edit: I understood the problem wrong. This is not a correct solution.

---

As far as I understood your problem you only need to iterate through all three lists, get all elements and add them together.

Here is a simple example with 3 lists of type String with your given example:

List<String> l1 = new ArrayList<String>();
l1.add("1.1");
l1.add("1.2");
l1.add("1.3");

List<String> l2 = new ArrayList<String>();
l2.add("2.1");

List<String> l3 = new ArrayList<String>();
l3.add("3.1");
l3.add("3.2");

for (String s1 : l1)
{
    for (String s2 : l2)
    {
        for (String s3 : l3)
        {
            System.out.println(s1 + " | " + s2 + " | " + s3);
        }
    }
}

which prints

1.1 | 2.1 | 3.1
1.1 | 2.1 | 3.2
1.2 | 2.1 | 3.1
1.2 | 2.1 | 3.2
1.3 | 2.1 | 3.1
1.3 | 2.1 | 3.2

What it does is quite simple: First we fill our three arrays with the values you want to create permutations of.

Then we can really just read the code: For every String s1 in the list l1 we take every String s2 in l2. For those combinations we take every string s3 in l3. Then we print out the combination

So what it internally does is:

s1  | s2  | s3
1.1 |     |
1.1 | 2.1 |
1.1 | 2.1 | 3.1 -> print
1.1 | 2.1 | 3.2 -> print
1.2 |     |
1.2 | 2.1 | 3.1 -> print
1.2 | 2.1 | 3.2 -> print
1.3 |     |
1.3 | 2.1 | 3.1 -> print
1.3 | 2.1 | 3.2 -> print

Answer 2

I think you have to do it recursively. It might be possible to use streams in Java 8 but i'm not (yet) so familiar with them. So here's how it would look using recursion:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class ArrayLists {

    ArrayList<List<String>> outer = new ArrayList(5);
    List<String> helper = new ArrayList<String>();

    public static void main(String[] args) {
        ArrayLists arrayLists = new ArrayLists();
        arrayLists.displayPermutations();
    }

    private void displayPermutations() {
        List<String> l1 = new ArrayList<String>();
        l1.add("1.1");
        l1.add("1.2");
        l1.add("1.3");

        List<String> l2 = new ArrayList<String>();
        l2.add("2.1");
        l2.add("2.2");

        List<String> l3 = new ArrayList<String>();
        l3.add("3.1");
        l3.add("3.2");
        l3.add("3.3");

        outer.add(l1);
        outer.add(l2);
        outer.add(l3);

        initHelper();
        recursion(l1);
    }

    private void initHelper() {
        for(int i = 0; i < outer.size(); i++) {
            helper.add(i, outer.get(i).get(0));
        }
    }

     void recursion(List<String> listToIncrement) {
         int helperIndex = outer.indexOf(listToIncrement);
         for(int i = 0; i < listToIncrement.size(); i++) {
             helper.set(helperIndex, listToIncrement.get(i));
             if(helperIndex < outer.size() - 1) {
                 recursion(outer.get(helperIndex + 1));
             }
            else{
                 System.out.println(helper);
             }

         }

    }
}

Of course, you can get rid of the initHelper method, it's not the cleanest code...

Answer 3

I think the keyword to your question is cartesian product rather than permutation. You can try something like this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BinaryOperator;
import java.util.function.Supplier;
import java.util.stream.Stream;

class Test{
    public static void main(String[] args){
        List<List<String>> totalList = new ArrayList<>();
        totalList.add(Arrays.asList("1.1","1.2","1.3"));
        totalList.add(Arrays.asList("2.1"));
        totalList.add(Arrays.asList("3.1","3.2"));
        Supplier<Stream<String>>[] sup = new Supplier[totalList.size()];

        for(int i = 0; i<totalList.size();i++){
            final int j = i;
            sup[i]= () -> totalList.get(j).stream();
        }

        Stream<String> result = cartesian((a, b) -> a+"|"+b, sup);
        result.forEach(System.out::println);
    }

    private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator, Supplier<Stream<T>>... streams) {
    return Arrays.stream(streams)
        .reduce((s1, s2) -> 
            () -> s1.get().flatMap(t1 -> s2.get().map(t2 -> aggregator.apply(t1, t2))))
        .orElse(Stream::empty).get();
    }
}

See this other SO questions for more information: Cartesian product of streams in Java 8 as stream (using streams only)

Cartesian product of arbitrary sets in Java