java - 如何在 Java 中创建值的组合？

Question

我有以下 map :Map<Integer,String[]> map = new HashMap<Integer,String[]>();

键是整数，值是数组(也可以用列表代替)。

现在，我想获得键值的所有可能组合。例如，假设 map 包含以下条目:

key 1: "test1", "stackoverflow"
key 2: "test2", "wow"
key 3: "new"

组合包括

("test1","test2","new")
("test1","wow","new")
("stackoverflow", "test2", "new")
("stackoverflow", "wow", "new")

为此我设想了一个方法 boolean hasNext()如果存在下一对，则返回 true，而第二个方法仅返回下一组值(如果有)。

如何做到这一点？ map 也可以替换为其他数据结构。

Answer 1

该算法本质上与十进制数的递增算法(“x -> x+1”)几乎相同。

这里是迭代器类:

import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.TreeSet;

public class CombinationsIterator implements Iterator<String[]> {

    // Immutable fields
    private final int combinationLength;
    private final String[][] values;
    private final int[] maxIndexes;

    // Mutable fields
    private final int[] currentIndexes;
    private boolean hasNext;

    public CombinationsIterator(final Map<Integer,String[]> map) {
        combinationLength = map.size();
        values = new String[combinationLength][];
        maxIndexes = new int[combinationLength];
        currentIndexes = new int[combinationLength];

        if (combinationLength == 0) {
            hasNext = false;
            return;
        }

        hasNext = true;

        // Reorganize the map to array.
        // Map is not actually needed and would unnecessarily complicate the algorithm.
        int valuesIndex = 0;
        for (final int key : new TreeSet<>(map.keySet())) {
            values[valuesIndex++] = map.get(key);
        }

        // Fill in the arrays of max indexes and current indexes.
        for (int i = 0; i < combinationLength; ++i) {
            if (values[i].length == 0) {
                // Set hasNext to false if at least one of the value-arrays is empty.
                // Stop the loop as the behavior of the iterator is already defined in this case:
                // the iterator will just return no combinations.
                hasNext = false;
                return;
            }

            maxIndexes[i] = values[i].length - 1;
            currentIndexes[i] = 0;
        }
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }

    @Override
    public String[] next() {
        if (!hasNext) {
            throw new NoSuchElementException("No more combinations are available");
        }
        final String[] combination = getCombinationByCurrentIndexes();
        nextIndexesCombination();
        return combination;
    }

    private String[] getCombinationByCurrentIndexes() {
        final String[] combination = new String[combinationLength];
        for (int i = 0; i < combinationLength; ++i) {
            combination[i] = values[i][currentIndexes[i]];
        }
        return combination;
    }

    private void nextIndexesCombination() {
        // A slightly modified "increment number by one" algorithm.

        // This loop seems more natural, but it would return combinations in a different order than in your example:
//      for (int i = 0; i < combinationLength; ++i) {

        // This loop returns combinations in the order which matches your example:
        for (int i = combinationLength - 1; i >= 0; --i) {
            if (currentIndexes[i] < maxIndexes[i]) {
                // Increment the current index
                ++currentIndexes[i];
                return;
            } else {
                // Current index at max: 
                // reset it to zero and "carry" to the next index
                currentIndexes[i] = 0;
            }
        }
        // If we are here, then all current indexes are at max, and there are no more combinations
        hasNext = false;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Remove operation is not supported");
    }

}

这里是示例用法:

final Map<Integer,String[]> map = new HashMap<Integer,String[]>();
map.put(1, new String[]{"test1", "stackoverflow"});
map.put(2, new String[]{"test2", "wow"});
map.put(3, new String[]{"new"});

final CombinationsIterator iterator = new CombinationsIterator(map);
while (iterator.hasNext()) {
    System.out.println(
        org.apache.commons.lang3.ArrayUtils.toString(iterator.next())
    );
}

它会准确打印您的示例中指定的内容。

---

附言实际上不需要 map ；它可以由一个简单的数组数组(或列表列表)代替。构造函数会变得更简单一些:

public CombinationsIterator(final String[][] array) {
    combinationLength = array.length;
    values = array;

    // ...

    // Reorganize the map to array - THIS CAN BE REMOVED.