组合：生成所有“状态” – 数组组合
我有一个整数数组： n[] 。
另外，我有一个数组（ Nr[] ）包含n.length整数。 我需要以下列方式生成n[]所有组合：
/* let n.length == 3 and Nr[0] = 2, Nr[1] = 3, Nr[2] = 3 */ n = {0, 0, 0}; n = {1, 0, 0}; n = {2, 0, 0}; n = {0, 1, 0}; n = {0, 2, 0}; n = {0, 3, 0}; n = {0, 0, 1}; ... n = {1, 1, 0}; n = {1, 2, 0}; n = {1, 3, 0}; n = {2, 1, 0}; n = {2, 2, 0}; n = {2, 3, 0}; n = {1, 1, 1}; ... n = {0, 1, 1}; // many others
目标是找到n所有组合，其中n[i]可以是0 to Nr[i] 。
我没有成功……如何在Java中解决它？ 或者不是Java …
您可能希望使用递归 ，尝试每个索引的所有可能性，并使用子数组递归调用 “没有”最后一个元素。
public static void printPermutations(int[] n, int[] Nr, int idx) { if (idx == n.length) { //stop condition for the recursion [base clause] System.out.println(Arrays.toString(n)); return; } for (int i = 0; i <= Nr[idx]; i++) { n[idx] = i; printPermutations(n, Nr, idx+1); //recursive invokation, for next elements } }
调用：
public static void main(String[] args) { /* let n.length == 3 and Nr[0] = 2, Nr[1] = 3, Nr[2] = 3 */ int[] n = new int[3]; int Nr[] = {2,3,3 }; printPermutations(n, Nr, 0); }
会得到你：
[0, 0, 0] [0, 0, 1] [0, 0, 2] [0, 0, 3] [0, 1, 0] [0, 1, 1] [0, 1, 2] [0, 1, 3] [0, 2, 0] [0, 2, 1] [0, 2, 2] [0, 2, 3] [0, 3, 0] [0, 3, 1] [0, 3, 2] [0, 3, 3] [1, 0, 0] [1, 0, 1] [1, 0, 2] [1, 0, 3] [1, 1, 0] [1, 1, 1] [1, 1, 2] [1, 1, 3] [1, 2, 0] [1, 2, 1] [1, 2, 2] [1, 2, 3] [1, 3, 0] [1, 3, 1] [1, 3, 2] [1, 3, 3] [2, 0, 0] [2, 0, 1] [2, 0, 2] [2, 0, 3] [2, 1, 0] [2, 1, 1] [2, 1, 2] [2, 1, 3] [2, 2, 0] [2, 2, 1] [2, 2, 2] [2, 2, 3] [2, 3, 0] [2, 3, 1] [2, 3, 2] [2, 3, 3]
但请注意 - 使用此方法会按照您的描述打印所有元素，但顺序与您的示例不同。
注意：与问题逻辑不同，以下代码是高级别的，与Java中的标准一样，例如3输入将从0到2（包括）计数，而不是0到3。
这可以在没有递归的情况下完成，如下所示：
public static void printPermutations(int... size) { int total = 1; for (int i : size) total *= i; int[] n = new int[size.length]; for (int value = 0; value < total; value++) { int remain = value; for (int i = size.length - 1; i >= 0; i--) { n[i] = remain % size[i]; remain /= size[i]; } System.out.println(Arrays.toString(n)); } }
测试
printPermutations(2, 3, 3);
产量
[0, 0, 0] [0, 0, 1] [0, 0, 2] [0, 1, 0] [0, 1, 1] [0, 1, 2] [0, 2, 0] [0, 2, 1] [0, 2, 2] [1, 0, 0] [1, 0, 1] [1, 0, 2] [1, 1, 0] [1, 1, 1] [1, 1, 2] [1, 2, 0] [1, 2, 1] [1, 2, 2]
作为Java 8流中的练习，这里有一个用于迭代或流式化排列的类。
如何使用：
// Using Iterator for (int[] n : Permutations.iterable(2, 3, 3)) System.out.println(Arrays.toString(n)); // Using streams Permutations.stream(2, 3, 3) .parallel() .map(Arrays::toString) // this will be done in parallel .forEachOrdered(System.out::println); // Getting all int[][] results = Permutations.get(2, 3, 3); for (int[] n : results) System.out.println(Arrays.toString(n));
这三个都产生与上面相同的输出。
这是代码：
class Permutations implements Spliterator, Iterator { public static Stream stream(int... sizes) { return StreamSupport.stream(spliterator(sizes), false); } public static Spliterator spliterator(int... sizes) { long total = sum(sizes); return (total == 0 ? Spliterators.emptySpliterator() : new Permutations(sizes.clone(), 0, total)); } public static Iterable iterable(int... sizes) { long total = sum(sizes); if (total == 0) return Collections.emptyList(); int[] clonedSizes = sizes.clone(); return new Iterable() { @Override public Iterator iterator() { return new Permutations(clonedSizes, 0, total); } @Override public Spliterator spliterator() { return new Permutations(clonedSizes, 0, total); } }; } public static int[][] get(int... sizes) { long total = sum(sizes); if (total == 0) return new int[0][]; if (total > Integer.MAX_VALUE) throw new IllegalArgumentException("Invalid sizes (overflow): " + Arrays.toString(sizes)); Permutations generator = new Permutations(sizes.clone(), 0, total); int[][] result = new int[(int) total][]; for (int i = 0; i < result.length; i++) result[i] = generator.next(); return result; } private static long sum(int[] sizes) { long total = 1; for (int size : sizes) { if (size < 0) throw new IllegalArgumentException("Invalid size: " + size); try { total = Math.multiplyExact(total, size); // Java 8+: Fail on overflow } catch (@SuppressWarnings("unused") ArithmeticException e) { throw new IllegalArgumentException("Invalid sizes (overflow): " + Arrays.toString(sizes)); } } return total; } private final int[] sizes; private final long end; private long next; Permutations(int[] sizes, long start, long end) { this.sizes = sizes; this.end = end; this.next = start; } @Override public boolean hasNext() { return (this.next < this.end); } @Override public int[] next() { if (this.next == this.end) throw new NoSuchElementException(); long value = this.next++; int[] arr = new int[this.sizes.length]; for (int i = arr.length - 1; i >= 0; i--) { arr[i] = (int) (value % this.sizes[i]); value /= this.sizes[i]; } return arr; } @Override public int characteristics() { // Note: Can easily be made SORTED by implementing a Comparator return ORDERED | DISTINCT | NONNULL | IMMUTABLE | SIZED | SUBSIZED; // not SORTED or CONCURRENT } @Override public long estimateSize() { return this.end - this.next; } @Override public boolean tryAdvance(Consumer action) { if (this.next == this.end) return false; action.accept(next()); return true; } @Override public Spliterator trySplit() { if (this.next > this.end - 2) return null; long split = (this.end - this.next) / 2 + this.next; Permutations prefix = new Permutations(this.sizes, this.next, split); this.next = split; return prefix; } @Override public void forEachRemaining(Consumer action) { Spliterator.super.forEachRemaining(action); } }