4
\$\begingroup\$

(See the next iteration.)

Given a positive \$N\$, the following class generates all possible non-empty sets \$A \in \mathcal{P}(\{0, 1, \dots, N - 1\})\$ in lexicographic order. Also, it provides a method that can be used to copy a combination to a list. I am seeking primarily guidance regarding the API design of the class.

CombinationGenerator.java:

package net.coderodde.util;

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

public class CombinationGenerator<T> {

    /**
     * The array holding indices to elements considered to be in a combination.
     * Only the first {@code k} indices are considered actually to encode an 
     * item in a combination.
     */
    private final int[] indexArray;

    /**
     * The current number of items in a combination.
     */
    private int k;

    public CombinationGenerator(int totalNumberOfItems) {
        checkTotalNumberOfItems(totalNumberOfItems);
        this.indexArray = new int[totalNumberOfItems];
    }

    public boolean generateNextCombination() {
        if (k == 0) {
            k = 1;
            return true;
        }

        if (indexArray[k - 1] < indexArray.length - 1) {
            indexArray[k - 1]++;
            return true;
        }

        for (int i = k - 2; i >= 0; --i) {
            if (indexArray[i] < indexArray[i + 1] - 1) {
                indexArray[i]++;

                for (int j = i + 1; j < k; ++j) {
                    indexArray[j] = indexArray[j - 1] + 1;
                }

                return true;
            }
        }

        ++k;

        if (k > indexArray.length) {
            return false;
        }

        for (int i = 0; i < k; ++i) {
            indexArray[i] = i;
        }

        return true;
    }

    public void loadCombination(List<T> all, List<T> target) {
        Objects.requireNonNull(all, "The list being sampled is null.");
        Objects.requireNonNull(target, 
                               "The list to hold the combination is null.");

        target.clear();

        for (int i = 0; i < k; ++i) {
            target.add(all.get(indexArray[i]));
        }
    }

    private void checkTotalNumberOfItems(int totalNumberOfItems) {
        if (totalNumberOfItems < 1) {
            throw new IllegalArgumentException(
                    "Total number of items is illegal: " + 
                    totalNumberOfItems + ".");
        }
    }

    public static void main(final String... args) {
        List<String> all = new ArrayList<>();

        all.add("A");
        all.add("B");
        all.add("C");
        all.add("D");
        all.add("E");

        int row = 1;
        List<String> combinationHolder = new ArrayList<>();
        CombinationGenerator generator = new CombinationGenerator(all.size());

        while (generator.generateNextCombination()) {
            generator.loadCombination(all, combinationHolder);
            System.out.printf("%2d: %s\n", row++, combinationHolder);
        }
    }
}

CombinationGeneratorTest.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class CombinationGeneratorTest {

    private CombinationGenerator generator;

    @Test
    public void test() {
        List<String> all = new ArrayList<>();
        List<String> target = new ArrayList<>();

        all.add("A");
        all.add("B");
        all.add("C");
        all.add("D");
        all.add("E");

        for (int i = 1; i <= all.size(); ++i) {
            int combinations = pow2(i) - 1;
            int count = 0;

            generator = new CombinationGenerator(i);

            while (generator.generateNextCombination()) {
                count++;
            }

            assertEquals(combinations, count);
        }
    }

    private static int pow2(int exp) {
        return 1 << exp;
    }
}
\$\endgroup\$
2
\$\begingroup\$
  1. Consider the iterator pattern with the methods hasNextCombination() and nextCombination(). Let your implementation follow the implications. Maybe you have to introduce a buffer. The loadCombination()-method inverts the responsibility and let you do strange things like clearing the given list if the client gives you messy data. The standard iterator pattern is the way to go. Pass your list of elements to the constructor of your Iterator. Make defensive copies to avoid side effects. Return the combination of the elements directly. The Client should be responsible to collect them in a list.
  2. Even this suggestion will be obsolete (1.). Do not check for "null" values. If the client gives you "null" then he should expect that the program will not work properly. Giving up the responsibility of the client to not pass null values has serious consequences for your source code. You will end up checking everything for null because you cannot count on anything. There are some exceptions to that which should be known: The parent of the root of a hierarchy may be null, lazy initialization is dealing with null and son find()-methods may return null that has to be evaluated immediatly. In all other cases: Never pass null, never check null and never return null.
  3. Break the generateNextCombination()-method into smaller pieces. If you experience problems then it surely has to do with the multiple return statements. Multiple return statements will hinder you to apply refactorings like "extract method". Furthermore: extending your code is much more predictable. Avoid multiple return statements in a method. Provide a proper control flow until the end of the method.
  4. As a matter of common usage do not use ++k. Use k++ instead. You yourself are switching between suffix and prefix notation. Keep doing one thing consistently to have the least surprise. Do not forget to adapt your breaking conditions.
  5. As it is used in the test, do not take my suggestion too serious here but: Avoid using bit shifting. I do not event know if there is a significant speed up. After all it doesn't matter until your application critical on this. And most of the applications aren't. The reason is you introduce low level language structures in a high level language.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.