Комбинаторика: генерировать все «состояния» - комбинации массивов

Question

У меня есть массив целых чисел: 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 ...

Answer 1

Возможно, вы захотите использовать рекурсию , попробовать все возможности для каждого индекса и рекурсивно вызвать с подрешеткой , "без" последнего элемента.

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]

Обратите внимание: при использовании этого метода печатаются все элементы, как вы описываете, но в другом порядке, чем в вашем примере.

Answer 2

Примечание: В отличие от логики вопроса, следующий код эксклюзивен сверху, как стандарт в 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<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);
    }

}