Algorithm to get all the combinations of size n from an array (Java)?

Question

Right now I'm trying to write a function that takes an array and an integer n, and gives a list of each size n combination (so a list of int arrays). I am able to write it using n nested loops, but this only works for a specific size of subset. I can't figure out how to generalize it to work for any size of combination. I think I need to use recursion?

This is the code for all combinations of 3 elements, and I need an algorithm for any number of elements.

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

public class combinatorics{
    public static void main(String[] args) {

        List<int[]> list = new ArrayList<int[]>();
        int[] arr = {1,2,3,4,5};
        combinations3(arr,list);
        listToString(list);
    }

    static void combinations3(int[] arr, List<int[]> list){
        for(int i = 0; i<arr.length-2; i++)
            for(int j = i+1; j<arr.length-1; j++)
                for(int k = j+1; k<arr.length; k++)
                    list.add(new int[]{arr[i],arr[j],arr[k]});
    }

    private static void listToString(List<int[]> list){
        for(int i = 0; i<list.size(); i++){ //iterate through list
            for(int j : list.get(i)){ //iterate through array
                System.out.printf("%d ",j);
            }
        System.out.print("\n");
        }
    }
}

Answer 1

This is a well-studied problem of generating all k-subsets, or k-combinations, which can be easily done without recursion.

The idea is to have array of size k keeping sequence of indices of elements from the input array (which are numbers from 0 to n - 1) in increasing order. (Subset then can be created by taking items by these indices from the initial array.) So we need to generate all such index sequences.

First index sequence will be [0, 1, 2, ... , k - 1], on the second step it switches to [0, 1, 2,..., k], then to [0, 1, 2, ... k + 1] and so on. The last possible sequence will be [n - k, n - k + 1, ..., n - 1].

On each step, algorithm looks for the closest to the end item which can be incremented, increments it and fills up items right to that item.

To illustrate, consider n = 7 and k = 3. First index sequence is [0, 1, 2], then [0, 1, 3] and so on... At some point we have [0, 5, 6]:

[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements

next iteration:

[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"

Thus, [0, 5, 6] is followed by [1, 2, 3], then goes [1, 2, 4] etc.

Code:

int[] input = {10, 20, 30, 40, 50};    // input array
int k = 3;                             // sequence length   

List<int[]> subsets = new ArrayList<>();

int[] s = new int[k];                  // here we'll keep indices 
                                       // pointing to elements in input array

if (k <= input.length) {
    // first index sequence: 0, 1, 2, ...
    for (int i = 0; (s[i] = i) < k - 1; i++);  
    subsets.add(getSubset(input, s));
    for(;;) {
        int i;
        // find position of item that can be incremented
        for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--); 
        if (i < 0) {
            break;
        }
        s[i]++;                    // increment this item
        for (++i; i < k; i++) {    // fill up remaining items
            s[i] = s[i - 1] + 1; 
        }
        subsets.add(getSubset(input, s));
    }
}

// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
    int[] result = new int[subset.length]; 
    for (int i = 0; i < subset.length; i++) 
        result[i] = input[subset[i]];
    return result;
}

Answer 2

If I understood your problem correctly, this article seems to point to what you're trying to do.

To quote from the article:

Method 1 (Fix Elements and Recur)

We create a temporary array ‘data[]’ which stores all outputs one by one. The idea is to start from first index (index = 0) in data[], one by one fix elements at this index and recur for remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for remaining indexes. When number of elements in data[] becomes equal to r (size of a combination), we print data[].

Method 2 (Include and Exclude every element)

Like the above method, We create a temporary array data[]. The idea here is similar to Subset Sum Problem. We one by one consider every element of input array, and recur for two cases:

1. The element is included in current combination (We put the element in data[] and increment next available index in data[])
2. The element is excluded in current combination (We do not put the element and do not change index)

When number of elements in data[] become equal to r (size of a combination), we print it.