java - 在 Java 中查找给定数组的所有可能组合

Question

我正在解决 Java 中的一个问题，通过将数组中每个项目的值一次递减一个，直到每个索引处达到值 1，找到给定任意起始数组的所有可能组合。

我已经开始执行下面的测试用例，但还没有走得太远。我需要一些帮助来解决我的问题。

import org.junit.Assert;
import org.junit.Test;

public class ComboTest
{
    @Test
    public void test()
    {
        int[][] answers = {
            {4, 3, 2}, {3, 3, 2}, {2, 3, 2}, {1, 3, 2}, 
            {4, 2, 2}, {3, 2, 2}, {2, 2, 2}, {1, 2, 2}, 
            {4, 1, 2}, {3, 1, 2}, {2, 1, 2}, {1, 1, 2},

            {4, 3, 1}, {3, 3, 1}, {2, 3, 1}, {1, 3, 1}, 
            {4, 2, 1}, {3, 2, 1}, {2, 2, 1}, {1, 2, 1}, 
            {4, 1, 1}, {3, 1, 1}, {2, 1, 1}, {1, 1, 1},
        };


        int[] start = {4, 3, 2};

        int dim = 1;
        for (int i = 0; i < start.length; i++)
        {
            dim *= start[i];
        }

        int[][] combos = new int[dim][start.length];

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

        for (int i = 1; i < combos.length; i++)
        {
            for (int j = 0; j < combos[i].length; j++)
            {
                int k = combos[i - 1][j] - 1;

                if (k < 1)
                {
                    k = start[j];
                }

                combos[i][j] = k;
            }
        }

        for (int i = 0; i < combos.length; i++)
        {
            for (int j = 0; j < combos[i].length; j++)
            {
                Assert.assertEquals(answers[i][j], combos[i][j]);
            }
        }
    }
}

Answer 1

这是一个简单的状态搜索问题。您有一个起始状态，并且可以按照某些条件扩展它(创建其子级)。在您的情况下，通过减少其中一个值，但不低于某个下限。

如果您不熟悉 DFS 或 BFS，我建议您阅读这些内容。同时，这是代码(也许解决方案不是您期望的格式，但您可以对其进行处理:D):

public class ComboTest {
    public static class Combo {
        private Integer[] values;

        public Combo(Integer[] values) {
            this.values = values;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + Arrays.hashCode(values);
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (!(obj instanceof Combo)) {
                return false;
            }
            Combo other = (Combo) obj;
            if (!Arrays.equals(values, other.values)) {
                return false;
            }
            return true;
        }

        @Override
        public String toString() {
            return Arrays.toString(values);
        }

    }

    public static Set<Combo> combos(Combo start, int lowerBound) {
        Set<Combo> answers = new HashSet<Combo>();

        compute(start, lowerBound, answers);

        return answers;
    }

    private static void compute(Combo start, int lowerBound, Set<Combo> answers) {
        Deque<Combo> dfsStack = new ArrayDeque<Combo>();

        dfsStack.push(start);

        while (!dfsStack.isEmpty()) {
            Combo current = dfsStack.pop();
            answers.add(current);

            for (Combo next : expand(current, lowerBound)) {
                if (!answers.contains(next)) {
                    dfsStack.push(next);
                }
            }
        }
    }

    private static List<Combo> expand(Combo current, int lowerBound) {
        List<Combo> nexts = new ArrayList<Combo>();

        for (int i = 0; i < current.values.length; i++) {
            if (current.values[i] > lowerBound) {
                Integer[] copyCurrent = Arrays.copyOf(current.values, current.values.length);
                copyCurrent[i]--;
                nexts.add(new Combo(copyCurrent));
            }
        }

        return nexts;
    }

    public static void main(String[] args) {
        Combo start = new Combo(new Integer[] { 4, 3, 2 });
        Set<Combo> combos = combos(start, 1);

        for (Combo combo : combos) {
            System.out.println(combo);
        }

        System.out.println(combos.size());
    }

}

输出:

[4, 3, 1]
[2, 1, 1]
[3, 2, 1]
[1, 1, 2]
[2, 2, 2]
[3, 3, 2]
[4, 3, 2]
[4, 2, 1]
[3, 1, 1]
[2, 1, 2]
[3, 2, 2]
[4, 1, 1]
[4, 2, 2]
[3, 1, 2]
[4, 1, 2]
[1, 3, 1]
[1, 2, 1]
[2, 3, 1]
[1, 3, 2]
[1, 1, 1]
[2, 2, 1]
[3, 3, 1]
[1, 2, 2]
[2, 3, 2]
24