java - 如何在Java中生成具有N个可能元素(M> N)的数组列表(全部长度为M)？

例如，如果元素是{1, 2} (n = 2)和m = 3，则该方法应生成一个类似于{[1,1,1],[1,1,2],[1,2,1],[2,1,1],[1,2,2],[2,2,1],[2,1,2],[2,2,2]}的数组列表。

我知道Python可以做类似y = itertools.product((1, 2), repeat=3)的事情，但是如何有效地在Java中实现这一点。我尝试提供一些初始List并使用以下内容来获取所需的内容，但是时间复杂度过高，而输入大时性能极差。

public static List<List<Integer>> permute (List<Integer> list, int need) {

    List<List<Integer>> result = new ArrayList<>();
    if (need--==0) {
        result.add(list);
        return result;
    }
    for (int current : list)
        insert(permute(list,need), current, result);
    return result;
}


private static void insert(List<List<Integer>> currentLists, int currentInt, List<List<Integer>> list) {
    for (List<Integer> currentList : currentLists) {
        int size = currentList.size();
        for (int i = 0; i <= size; i++) {
            List<Integer> newList = new LinkedList<>();
            newList.addAll(currentList);
            newList.add(i, currentInt);
            list.add(newList);
        }
    }
}

最佳答案

使用库StreamEx解决方案如下所示:

    List<Integer> list = Arrays.asList(1, 2);
    int need = 3;
    StreamEx<List<Integer>> product = StreamEx.cartesianPower(need, list);

您可以使用并行处理或仅消耗部分延迟生成的结果来提高效率。

普通的旧Java中的另一种懒惰解决方案将创建可延迟产生排列的Iterator

class Permutator<T> implements Iterable<List<T>> {

    final List<T> items;
    final int homMuch;

    Permutator(List<T> items, int homMuch) {
        this.items = items;
        this.homMuch = homMuch;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {
            static final int OVERFLOW = -1;
            final int[] permutation = new int[homMuch];
            final int max = items.size();

            @Override
            public boolean hasNext() {
                for (int item : permutation) {
                    if (item == OVERFLOW) {
                        return false;
                    }
                }
                return true;
            }

            @Override
            public List<T> next() {
                ArrayList<T> result = new ArrayList<>(permutation.length);
                for (int index : permutation) {
                    result.add(items.get(index));
                }

                inc(permutation, 0);           // generate next permutation

                return result;
            }

            private void inc(int[] indexes, int index) {
                if (index >= indexes.length) {
                    for (int i = 0; i < indexes.length; i++) {
                        indexes[i] = OVERFLOW;
                    }
                    return;
                }
                int nextValue = indexes[index] + 1;
                if (nextValue < max) {
                    indexes[index] = nextValue;
                } else {
                    indexes[index] = 0;
                    inc(indexes, index + 1);
                }
            }

        };
    }
}

这样的生成器可以在循环中延迟使用

List<String> list = Arrays.asList("one", "two");
int need = 3;
for (List<String> permutation : new Permutator<>(list, need)) {
    System.out.println(permutation);
}

输出:

[one, one, one]
[two, one, one]
[one, two, one]
[two, two, one]
[one, one, two]
[two, one, two]
[one, two, two]
[two, two, two]