all possible x-part combinations of variable amount of items

Question

If I got an array like this:

String[] items = { "Cat", "Frog", "Dog", "Ferret"};

For example, all 3-item combinations in this case would be (if I didn't miss any):

String[][] combinations = { 
{ "Cat", "Frog", "Dog" }, 
{ "Cat", "Dog", "Ferret" },
{ "Cat", "Frog", "Ferret" }, 
{ "Frog", "Dog", "Ferret" } };

How can I get all possible x-item combinations of a variable amount of items using a java method?

Check this post, http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — LorenzoR, Nov 26 '13 at 02:46

jonasnas · Answer 1 · 2013-11-26T09:25:14.233

You could use combinatoricslib

There is also a function in apache commons math development version which generates integer combinations: CombinatoricsUtils.combinationsIterator (3.3)

You could use that function to generate indexes for you String array and then use those indexes to populate data with actual value.

public static Iterator<int[]> combinationsIterator(int n, int k)
Returns an iterator whose range is the k-element subsets of {0, ..., n - 1} represented as int[] arrays. The arrays returned by the iterator are sorted in descending order and they are visited in lexicographic order with significance from right to left. For example, combinationsIterator(4, 2) returns an Iterator that will generate the following sequence of arrays on successive calls to next(): [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]

EDIT:

As OP mentioned, this is a development version at the moment so to download you would have to checkout their source from here: source and then build it yourself (with maven)

Hmm, this does seem to only exist in the development-version 3.3. I could only find version 3.2 for download on http://commons.apache.org/proper/commons-math/download_math.cgi. Maybe there is another page where I can download the development jar or better a method which works the same way in 3.2? — Zulakis, Nov 26 '13 at 03:44
I updated my answer to add another lib you could use and also the source location of the apache-math which you could use to checkout the source and build it yourself with 'mvn package' — jonasnas, Nov 26 '13 at 09:27

score 0 · Answer 2 · answered Nov 26 '13 at 19:50

I solved it like this:

static void combinations2(String[] arr, int len, int startPosition, String[] result, ArrayList<String[]> allResults){
    if (len == 0){
        String[] copy = new String[result.length];
        System.arraycopy(result,0,copy,0,result.length);
        allResults.add(copy);
        return;
    }
    for (int i = startPosition; i <= arr.length-len; i++){
        result[result.length - len] = arr[i];
        combinations2(arr, len-1, i+1, result, allResults);
    }
}

Usage example:

ArrayList<String[]> allResults = new ArrayList<String[]>();
String[] items = { "Cat", "Frog", "Dog", "Ferret"};
combinations2(items, 3, 0, new String[3], allResults);

all possible x-part combinations of variable amount of items

2 Answers2