HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Generic class to generate combinations

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
genericgenerateclasscombinations

Problem

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 generate(int length, int choosen){
    List 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 -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

Solution

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.

Context

StackExchange Code Review Q#141305, answer score: 3

Revisions (0)

No revisions yet.