Combinatorics: generate all "states" - combinations of arrays

Question

I have an array of integers: n[] .

In addition, I have an array ( Nr[] ) containing n.length integers. I need to generate all n[] combinations as follows:

 /* 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 

The goal is to find all combinations of n , where n[i] can be 0 to Nr[i] .

I failed ... How to solve it in Java? Or not in Java ...

Answer 1

You might want to use recursion , try all the features for each index, and call the last element recursively using Subarray , without.

 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 } } 

call with:

 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); } 

You'll get:

 [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] 

Note, however, that using this method prints all the elements as you describe, but in a different order than your example.

Answer 2

Note. . Unlike the logic of the question, the following code is top-exclusive, like the standard in Java, for example. input 3 will be counted from 0 to 2 (inclusive), and not from 0 to 3.

This can be done without recursion as follows:

 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)); } } 

Test

 printPermutations(2, 3, 3); 

Exit

 [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] 

---

As an exercise in Java 8 threads, here is a class for iterating or streaming permutations.

How to use:

 // 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)); 

All three produce the same conclusion as above.

Here is the code:

 class Permutations implements Spliterator<int[]>, Iterator<int[]> { public static Stream<int[]> stream(int... sizes) { return StreamSupport.stream(spliterator(sizes), false); } public static Spliterator<int[]> spliterator(int... sizes) { long total = sum(sizes); return (total == 0 ? Spliterators.emptySpliterator() : new Permutations(sizes.clone(), 0, total)); } public static Iterable<int[]> iterable(int... sizes) { long total = sum(sizes); if (total == 0) return Collections.emptyList(); int[] clonedSizes = sizes.clone(); return new Iterable<int[]>() { @Override public Iterator<int[]> iterator() { return new Permutations(clonedSizes, 0, total); } @Override public Spliterator<int[]> 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<int[]> 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<? super int[]> action) { if (this.next == this.end) return false; action.accept(next()); return true; } @Override public Spliterator<int[]> 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<? super int[]> action) { Spliterator.super.forEachRemaining(action); } }