4
\$\begingroup\$

I have refactored the previous combination generator, and now it is an iterator returning combinations as lists. It hides larger constant factors as the previous version, yet it is really easy to use:

for (List<String> combination : new CombinationIterable<>(allStrings)) {
    System.out.println(combination);
}

CombinationIterable.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class CombinationIterable<T> implements Iterable<List<T>> {

    private final List<T> allElements;

    public CombinationIterable(List<T> allElements) {
        this.allElements = new ArrayList<>(allElements);
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new CombinationIterator<>(allElements);
    }

    private static final class CombinationIterator<T> 
    implements Iterator<List<T>> {

        private final List<T> allElements;
        private final int[] indices;
        private List<T> nextCombination;
        private int currentCombinationSize;

        CombinationIterator(List<T> allElements) {
            this.allElements = new ArrayList<>(allElements);
            this.indices = new int[allElements.size()];

            if (!allElements.isEmpty()) {
                // Create the first combination.
                currentCombinationSize = 1;
                nextCombination = new ArrayList<>(1);
                nextCombination.add(allElements.get(0));
            }
        }

        @Override
        public boolean hasNext() {
            return nextCombination != null;
        }

        @Override
        public List<T> next() {
            if (nextCombination == null) {
                throw new NoSuchElementException("No combinations left.");
            }

            List<T> combination = nextCombination;
            generateNextCombination();
            return combination;
        }

        private void loadCombination() {
            List<T> combination = new ArrayList<>(currentCombinationSize);

            for (int i = 0; i < currentCombinationSize; ++i) {
                combination.add(allElements.get(indices[i]));
            }

            this.nextCombination = combination;
        }

        private void generateNextCombination() {
            if (indices[currentCombinationSize - 1] < indices.length - 1) {
                indices[currentCombinationSize - 1]++;
                loadCombination();
                return;
            }

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

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

                    loadCombination();
                    return;
                }
            }

            ++currentCombinationSize;

            if (currentCombinationSize > indices.length) {
                this.nextCombination = null;
                return;
            }

            for (int i = 0; i < currentCombinationSize; ++i) {
                indices[i] = i;
            }

            loadCombination();
        }
    }

    public static void main(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;

        for (List<String> combination : new CombinationIterable<>(all))  {
            System.out.printf("%2d: %s\n", row++, combination);
        }
    }
}

CombinationIterableTest.java:

package net.coderodde.util;

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

public class CombinationIterableTest {

    private CombinationIterable generator;

    @Test
    public void test() {
        List<String> all = 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) {
            List<String> list = new ArrayList<>();

            for (int j = 0; j < i; ++j) {
                list.add(all.get(j));
            }

            int combinations = pow2(i) - 1;
            int count = 0;

            for (List<String> combination : new CombinationIterable<>(list)) {
                ++count;
            }

            assertEquals(combinations, count);
        }
    }

    private static int pow2(int exp) {
        return 1 << exp;
    }
}

Is there anything to improve?

\$\endgroup\$
3
  • 2
    \$\begingroup\$ In theory, you could just use a single loop for 0 to 2^all.size() and use bitand'ing to choose which elements to include. You could also create this as array of strings, then sort them and split them back into sets. \$\endgroup\$
    – user1149
    Commented Feb 13, 2016 at 20:12
  • \$\begingroup\$ I don't understand what bitand'ing you are talking about; please consider providing an answer. \$\endgroup\$
    – coderodde
    Commented Feb 14, 2016 at 10:50
  • \$\begingroup\$ rosettacode.org/wiki/Power_set#Binary_String is what I had in mind. \$\endgroup\$
    – user1149
    Commented Feb 14, 2016 at 15:53

2 Answers 2

2
\$\begingroup\$

Only minor remarks - not so much related to the code itself, but rather to the concepts:


In your previous question, you emphasized that the combinations should be returned in lexicographic order. From my understanding, this is not the case: The output is

 1: [A]
 2: [B]
 3: [C]
 4: [D]
 5: [E]
 6: [A, B]
 7: [A, C]
 8: [A, D]
 9: [A, E]
...

Imagining these as "words in a dictionary" (in line with the Wikipedia page about lexicographical_order), "AB" would come before "B" - but maybe this is just a misinterpretation on my side, and you are considering the words to be "filled with some character that comes before 'A'" at the beginning, as in

____A
____B
____C
...
___AB
___AC
...
_ABCD
_ABCE
...
ABCDE

The word "Combination" usually has a predefined meaning that differs from how you use it: A Combination is usually a selection of a certain number of elements from a given set. (Differentiated between "combinations with repetition" and "combinations without repetition").

What you are computing there are actually the elements of the Power Set of the given list (which usually also involves the empty list - but this is just a detail).

This is also what the comments referred to: When looking closely at the elements of the power set, you'll see a resemblance of these elements and the bit patterns of the binary representations of numbers:

               EDCBA   Result:
0   binary:    00000   {     }
1   binary:    00001   {    A}
2   binary:    00010   {   B }
3   binary:    00011   {   BA}
...
9   binary:    01001   { D  A}
...
31  binary:    11111   {EDCBA}

This can be imagined as "taking the elements into the result when the binary representation of the corresponding number has a '1' at the respective position".

Unfortunately, the order would then be different from your current one, so this may not be applicable here.


In terms of API design, there is probably not much more to say: The implementation as an Iterable makes it very easy to use it, as there are only two (relevant) public methods with well-known semantics, and, as far as I can see, they are implemented properly. One could consider different, minor restructurings of the private parts, but none that would objectively be "better" than the current solution.


A side note: A while ago I created some similar classes at https://github.com/javagl/Combinatorics . They are also implemented as Iterables, including a CombinationIterable, but as mentioned above, this computes combinations - in contrast to the PowerSetIterable, which computes the power set that you actually seem to be looking for - it contains a few words about the implementation using the binary number representations.

\$\endgroup\$
0
\$\begingroup\$

On their own, your combinatorics Iterables look pretty generic.

  • Given that they are Iterables rather than Lists or Collections, one consideration would be instantiation with an Iterable.

Another thing to ponder would be the name itertools.
Even with "the basic three", this seems to call for common base classes - I gave it a try, without proper attention to other concerns. (One thing I'm never quite comfortable with is visibility: protected exposes quite a lot.) I didn't succeed in integrating Partitions without a second type parameter:

/** several classes for combinatorics */
abstract class Combinics {
 /** Instantiated with a List of elements of type {@code E}, for
  *  one type of aggregation of elements represented as {@code
  *  List<I>} support iteration through all these aggregations.
  * Elements at different positions are considered different. */
    static abstract class Iterable<E, I>
        implements java.lang.Iterable<List<I>> {

        protected final /*E*/Object[] allElements;

        /*final*/ int param;

        public Iterable(List<E> allElements) {
            final int count = allElements.size();
            if (0 == count)
                this.allElements = null;
            else {
            //  E first = allElements.get(0);
                this.allElements = allElements.toArray(
            // off: allElements need not be of uniform type
            //      (E[]) Array.newInstance(first.getClass(), count)
                    );
            }
        }
    }
 /** Instantiated with a List of elements of type {@code E}, for
  *  one type of aggregation of elements represented as {@code
  *  List<I>} support iteration through all these aggregations.
  * Elements at different positions are considered different. */
    static abstract class Iterator<E, I> 
        implements java.util.Iterator<List<I>> {


        final /*E*/Object[] allElements;
        final int[] indices;
    // ArrayList for extended interface - YAGNI?
        ArrayList<I> next;

        @SuppressWarnings("unchecked")
        E get(int index) {
            return (E) allElements[index];
        }

        Iterator(List<? extends E> allElements) {
            this(allElements, allElements.size());
        }

        Iterator(List<? extends E> allElements, int count) {
            indices = new int[count];
            if (0 == count)
                this.allElements = null;
            else {
                E first = allElements.get(0);
                this.allElements = allElements.toArray(
                // slightly off: allElement need not be of uniform type
                    (E[]) java.lang.reflect.Array.newInstance(
                        first.getClass(), count)
                    );
            }
        }

        Iterator(Object[] allElements, int count) {
            indices = new int[count];
            this.allElements = allElements;
        }
        protected int size() { return indices.length; }

        @Override
        public boolean hasNext() {
            return next != null;
        }
    /** for messages and more */// cache? nah...
        protected String singular() {
            String className = getClass().getName();
            int
                lastDot = className.lastIndexOf('.')+1,
                lastIter = className.indexOf("Iter", lastDot);
            if (0 <= ".$".indexOf(className.charAt(lastIter-1)))
                lastIter -= 1;
            return className.substring(lastDot,
                lastIter).toLowerCase();
        }
    /** for messages and more */
        protected String plural() { return singular() + 's'; }

        @Override
        public List<I> next() {
            if (next == null) {
                throw new NoSuchElementException(
                    "No " + plural() + " left.");
            }

            List<I> current = next;
            generateNext();
            return current;
        }
    /** Generates and keeps the next aggregation. */
        abstract void generateNext();
    /** non-public in java.util.Arrays */
        protected static void swap(int[] array, int a, int b) {
            int tmp = array[a];
            array[a] = array[b];
            array[b] = tmp;
        }
    }

 /** Instantiated with a List of elements of type {@code E},
  * for combinations of elements represented as {@code List<E>}
  * support iteration through all these combinations.
  * Elements at different positions are considered different. */
    static abstract class IterElements<T> extends Iterator<T, T> {
        IterElements(List<T> allElements) { super(allElements); }
        IterElements(List<T> allElements, int count) {
            super(allElements, count);
        }
        IterElements(Object[] allElements, int count) {
            super(allElements, count);
        }

        protected void load() {
            next = new ArrayList<>(size());

            for (int i = 0; i < size() ; ++i) {
                next.add(get(indices[i]));
            }
        }
    }

    static void
    demo(int count, Function<List<?>, Iterable<?, ?>> generator) {
        List<String> all = new ArrayList<>(count);
        for (char c = 'A', end = (char) ('A' + count) ; c < end ; c++)
            all.add(String.valueOf(c));

        int row = 1;

        for (List<String> elements : (Iterable<String, String>)
                generator.apply(all))  {
            System.out.printf("%2d: %s\n", row++, elements);
        }
    }
}

/** Instantiated with a List of elements of type {@code E},
 * for combinations of elements represented as {@code List<E>}
 * support iteration through all these combinations.
 * Elements at different positions are considered different. */
public class Combination<E> extends Combinics.Iterable<E, E> {

    public Combination(List<E> allElements, int nElements) {
        super(allElements);
        param = nElements;
    }
    public Combination(List<E> allElements) { this(allElements, -1); }

    @Override
    public java.util.Iterator<List<E>> iterator() {
        return param < 0 ? new Iterator<E>(allElements)
            : new Iterator<E>(allElements, param);
    }
 /** Instantiated with a List of elements of type {@code E},
  * for combinations of elements represented as {@code List<E>}
  * support iteration through all these combinations.
  * Elements at different positions are considered different. */
    static class Iterator<E> extends Combinics.IterElements<E> {
        int currentSize;
        Iterator(List<E> allElements) {
            this(allElements, 1, allElements.size());
        }
        Iterator(List<E> allElements, int count) {
            this(allElements, count, count);
        }
        Iterator(List<E> allElements, int start, int end) {
            super(allElements, end);
            init(start);
        }
        void init(int start) {
            if (0 != indices.length) {
                // Create the first combination.
                currentSize = start;
                next = new ArrayList<>(currentSize);
                for (int i = 0; i < currentSize; ++i)
                    indices[i] = i;
                load();
            }
        }
        Iterator(Object... allElements) {
            this(allElements, 1, allElements.length);
        }
        Iterator(Object[] allElements, int param) {
            this(allElements, param, param);
        }
        Iterator(Object[] allElements, int start, int end) {
            super(allElements, end);
            init(start);
        }
//      @Override
//      protected String singular() { return "combination"; }

        @Override
        protected int size() { return currentSize; }

        @Override
        void generateNext() {
            next = new ArrayList<E>(next); // late?
            if (indices[currentSize - 1] < allElements.length - 1) {
                indices[currentSize - 1]++;
                next.set(currentSize - 1, get(indices[currentSize-1]));
                return;
            }

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

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

                    load();
                    return;
                }
            }

            if (indices.length < ++currentSize) {
                next = null;
                return;
            }

            for (int i = 0; i < currentSize; ++i) {
                indices[i] = i;
            }

            load();
        }
    }

    public static void main(String[] args) {
        Combinics.demo(5, (all) -> new Combination<>(all));
        Iterator<String> combinations =
            new Combination.Iterator<String>(
                Arrays.asList("A", "B", "C", "D", "E"), 3);
    // provoke Exception
        for (List<String> combi ;
             null != (combi = combinations.next()) ; ) {
            System.out.println(combi);
        }
    }
}



public class PartitionIterable<E>
    extends Combinics.Iterable<E, List<E>> {

    private final int blocks;

    public PartitionIterable(List<E> allElements, int blocks) {
        super(allElements);
        checkNumberOfBlocks(blocks, allElements.size());
        this.blocks = blocks;
    }

    @Override
    public Iterator<List<List<E>>> iterator() {
        return new PartitionIterator<>(allElements, blocks);
    }

    private void
    checkNumberOfBlocks(int blocks, int numberOfElements) {
        if (blocks < 1) {
            throw new IllegalArgumentException(
                "The number of blocks should be at least 1, received: "
                + blocks);
        }

        if (blocks > numberOfElements) {
            throw new IllegalArgumentException(
                "The number of blocks should be at most "
                + numberOfElements + ", received: " + blocks);
        }   
    }

    private static class PartitionIterator<E> 
        extends Combinics.Iterator<E, List<E>> {

        private final int blocks;

        private final int[] s;
        private final int[] m;
        private final int n;

        PartitionIterator(List<E> allElements, int blocks) {
            super(allElements);
            this.blocks = blocks;
            this.n = allElements.size();

            s = indices;//new int[n];
            m = new int[n];

            if (n != 0) {
                for (int i = n - blocks + 1; i < n; ++i) {
                    s[i] = m[i] = i - n + blocks;
                }

                loadPartition();
            }
        }
        @Override
        protected String singular() { return "partition"; }

        private void loadPartition() {
            next = new ArrayList<>(blocks);

            for (int i = 0; i < blocks; ++i) {
                next.add(new ArrayList<>());
            }

            for (int i = 0; i < n; ++i) {
                next.get(s[i]).add(allElements.get(i));
            }
        }

        @Override
        void generateNext() {
            for (int i = n - 1; i > 0; --i) {
                if (s[i] < blocks - 1 && s[i] <= m[i - 1]) {
                    s[i]++;
                    m[i] = Math.max(m[i], s[i]);

                    int limit = n - blocks + m[i] + 1;
                    for (int j = i + 1; j < limit; ++j) {
                        s[j] = 0;
                        m[j] = m[i];
                    }

                    for (int j = limit; j < n; ++j) {
                        s[j] = m[j] = blocks - n + j;
                    }

                    loadPartition();
                    return;
                }
            }

            next = null;
        }
    }

    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C", "D");
        int row = 1;

        for (int blocks = 1; blocks <= list.size(); ++blocks) {
            for (List<List<String>> partition : 
                    new PartitionIterable<>(list, blocks)) {
                System.out.printf("%2d: %s\n", row++, partition);
            }
        }
    }
}

class PermutationIterable<T>
    extends Combinics.Iterable<T, T> {

    public PermutationIterable(List<T> allElements) {
        super(allElements);
    }

    @Override
    public java.util.Iterator<List<T>> iterator() {
        return new Iterator<>(allElements);
    }

    private static final class Iterator<T>
        extends Combinics.IterElements<T> {

        Iterator(List<T> allElements) {
            super(allElements);
            if (allElements.isEmpty())
                next = null;

            for (int i = 0; i < indices.length; ++i) {
                indices[i] = i;
            }

            next = new ArrayList<>(allElements);
        }
//        @Override
//        protected String singular() { return "permutation"; }

        void generateNext() {
            int i = indices.length - 2;

            while (i >= 0 && indices[i] > indices[i + 1]) {
                --i;
            }

            if (i == -1) {
                // No more new permutations.
                next = null;
                return;
            }

            int j = i + 1;
            int min = indices[j];
            int minIndex = j;

            while (j < indices.length) {
                if (indices[i] < indices[j] && indices[j] < min) {
                    min = indices[j];
                    minIndex = j;
                }

                ++j;
            }

            swap(indices, i, minIndex);

            ++i;
            j = indices.length - 1;

            while (i < j) {
                swap(indices, i++, j--);
            }

            load();
        }
    }

    public static void main(final String... args) {
        Combinics.main(4,
            (alphabet) -> new PermutationIterable<>(alphabet));
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ ran out of time: numerical parameter used with python's itertools combinations is there, toDo: permutations, partitions,… \$\endgroup\$
    – greybeard
    Commented Feb 15, 2016 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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