Generic class to generate combinations

Question

As junior java programmer I am working with Euler project and I would like to create a general purpose class which generates all the combinations from the length and number of choosen elements. The class returns a list of boolean arrays with length of length. Each array has choosen true value which highlight the chosen elements the others are false. I have a working solution (I mean it is tested to small numbers) but I wonder is there any opportunity to improve the performance or improve some other aspect. Here it is:

public static List<boolean[]> generate(int length, int choosen){
    List<boolean[]> variationList = new ArrayList<>();
    boolean[] actual = initArray(length, choosen);
    variationList.add(actual.clone());
    while(incrementArray(actual)) {
        variationList.add(actual.clone());
    }
    return variationList;
}


private static boolean[] initArray(int length, int choosen) {
    boolean[] array = new boolean[length];
    for (int index=0; index<choosen; index++) {
        array[index] = true;
    }
    return array;
}

private static boolean incrementArray(boolean[] actual) {
    for(int index = actual.length-1; index > -1 ; index--) {
        if(actual[index]) {
            if(moveForward(actual, index)) {
                return true;
            }
        }
    }
    return false;
}

private static boolean moveForward(boolean[] actual, int position) {
    if(position<actual.length-1 && !actual[position+1]) {
        actual[position] = false;
        actual[position+1] = true;
        copyBack(actual, position);
        return true;
    }else {
        return false;
    }
}

private static boolean copyBack(boolean[] actual, int position) {
    boolean answer = false;
    int delay = 2;
    for (int index = position+2; index<actual.length;index++) {
        if(actual[index]) {
            actual[index] = false;
            actual[position + delay] = true;
            delay++;
            answer = true;
        }
    }
    return answer;
}

Edit

Euler project was only the motive I would like to find a way independently. My aim was produce all of the combinations (by the way my solution for the original problem needed them all (not just the number of them) but there is a workaround which no need combination at all). Some example of the method:

CombinationGenerator.generate(5, 1);

The result:

true false false false false
false true false false false
false false true false false
false false false true false
false false false false true

Invocation:

CombinationGenerator.generate(5, 3)

The result:

true true true false false
true true false true false
true true false false true
true false true true false
true false true false true
true false false true true
false true true true false
false true true false true
false true false true true
false false true true true

Answer 1

BitSet

A BitSet is deliberately designed to be a memory efficient way to hold Boolean values.

It also has initialize methods (clear and set) already, so no need for initArray. In combination with nextSetBit and nextClearBit (or the previous variants), those methods can replace moveForward. And copyBack isn't necessary without moveForward.

The single increment for loop in incrementArray would not be necessary with a BitSet. Again, the nextSetBit and previousSetBit methods would allow you to jump through multiple steps at once.

I haven't compared performance, but generally built-in methods are more efficient than custom methods. The counter-argument here might be that a BitSet is more space efficient than time efficient. Or that using the built-in methods involves algorithmic tradeoffs. You'd have to test to see.

Nitpick

Choosen is not a word. Although the base word is choose, the past participle is chosen with a single o. But the variable doesn't really hold what has been chosen. It holds a count of how many choices should be set to true. The BitSet definition suggests that the best name for this is cardinality. At least that's the name of the BitSet method.

BitSet also uses size to represent the total number of choices. And uses length for something else. Consider switching the parameter name length to size to match. Not because length is a bad name, just inconsistent with BitSet.

Answer 2

Try solving recursively where in each call you have to cases: appending 1 to an array and 0 (note that you do both each time). When you append 1, then you need to count if you have reached the chosen count or length, if not then call recursively on that array. Do the same for appending 0 except for you don't need to count if you exceeded choose limit.

Code is something like this (I use c++ but it is easily translatable to Java):

void gen_recursively(vector< vector<bool> > &combinations, vector<int> &current_combination, int len, int chosen) {
    if(current_combination.size() != len) {
        vector<int> current_with_0 = current_combination;
        current_with_0.push_back(0);
        gen_recursively(combinations, current_combination_with_0, len, chosen);

        vector<int> current_with_1 = current_combination;
        current_with_0.push_back(1);
        if(count_chosen(current_with_1)) {
            combinations.push_back(padd_with_zeros_at_end(current_with_1, len));
        } else {
            gen_recursively(combinations, current_combination_with_1, len, chosen);
        }
    } else {
        combinations.push_back(current_combination);
    }
}