How can one find all possible groups of 4 in a list using Java?

Question

Let's say I have a list of letters:

String list[] = {"A","B","C","D","E","F","G","H","I","J"};

What's the simplest way to find all possible groups of 4 in a list using Java (given that the order isn't important, meaning ABCD would be the same as DCBA)?

I came across this What's the quickest way to find all possible pairs in list? and I tried to extend the solution there by doing this:

    for(int i=0;i<=list.length-4;i++){
        for(int j=i+1;j<=list.length-3;j++){
            for(int k=i+2;k<=list.length-2;k++){
                for(int l=i+3;l<=list.length-1;l++){
                    System.out.println(list[i]+","+list[j]+","+list[k]+","+list[l]);
                }
            }
        }
    }
}

But it became obvious quite fast that that isn't right. If anyone could help provide a solution that is an extension of the solution from the link above, that would be nice to have. Thanks!

James_D · Answer 1 · 2014-05-16T03:15:42.737

I doubt this is fastest, or most efficient by any measure, but I like it (and it's more general).

This basically says to get all combinations of size k from a (sorted) list of n elements, take each of the n-k+1 first elements in turn, and append all combinations of size k-1 from the elements in the list that come after it.

To terminate the recursion, if k=1, just return a list of singleton lists of each of the elements.

To make that concrete, in your example, it does:

"A", with all possible combinations of 3 letters from "B"-"J" appended

along with

"B", with all possible combinations of 3 letters from "C"-"J" appended

along with

"C", with all possible combinations of 3 letters from "D"-"J" appended

...

"F", with all possible combinations of 3 letters from "G"-"J" appended

along with

"G", with all possible combinations of 3 letters from "H"-"J" appended (there is only 1)

To get all possible combinations of 3 letters from "B"-"J", it does

"B", with all possible combinations of 2 letters from "C"-"J" appended

along with

"C", with all possible combinations of 2 letters from "D"-"J" appended

etc

The combinations are produced in lexographical order, with respect to the initial ordering of the list.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class Combinatorics {

    /**
     * Computes all combinations of items of size <code>size</code>
     * Assumes that items contains no replicates<
     * @param items
     * @param size
     * @return A List of all possible Lists of items, each List of size <code>size</code>.
     */
    public static <T extends Comparable<? super T>> List<List<T>> combinations(List<T> items, int size) {
        if (size == 1) {
            List<List<T>> result = new ArrayList<>();
            for (T item : items) {
                result.add(Collections.singletonList(item));
            }
            return result ;
        }
        List<List<T>> result = new ArrayList<>();
        for (int i=0; i <= items.size() - size; i++) {
            T firstItem = items.get(i);
            List<List<T>> additionalItems = combinations(items.subList(i+1, items.size()), size-1) ;
            for (List<T> additional : additionalItems) {
                List<T> combination = new ArrayList<>();
                combination.add(firstItem);
                combination.addAll(additional);
                result.add(combination);
            }
        }
        return result ;
    }

    public static void main(String[] args) {
        List<String> values = Arrays.asList("A", "C", "B", "D", "E", "F", "G", "H", "I", "J");
        List<List<String>> allCombinations = combinations(values, 4);
        for (List<String> combination : allCombinations) {
            System.out.println(combination);
        }
        System.out.println(allCombinations.size() + " total combinations");
    }
}

BevynQ · Accepted Answer · 2014-05-16T02:23:34.650

You were close try this.

for(int i=0;i<=list.length-4;i++){
    for(int j=i+1;j<=list.length-3;j++){
        for(int k=j+1;k<=list.length-2;k++){// change i+2 to j+1
            for(int l=k+1;l<=list.length-1;l++){// change i+3 to k+1
                System.out.println(list[i]+","+list[j]+","+list[k]+","+list[l]);
            }
        }
    }
}

edit

The i + x initial will cause problems because they are static offsets and do on prevent index collisions. i.e. when j increments j+1 will equal i+2 causing a collision. By making the offset j+1 instead of i+2 it becomes a dynamic offset in relation to j preventing the collision.

How can one find all possible groups of 4 in a list using Java?

2 Answers2