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;
}