Учитывая массив целых чисел [x0 x1 x2], как рассчитать все возможные перестановки от [0 0 0] до [x0 x1 x2]? - PullRequest
Новая
       39

Учитывая массив целых чисел [x0 x1 x2], как рассчитать все возможные перестановки от [0 0 0] до [x0 x1 x2]?

4 голосов
/ 19 апреля 2010

Я пишу программу, которая принимает ArrayList, и мне нужно вычислить все возможные перестановки, начиная со списка нулей, до значения в соответствующем списке ввода.

Кто-нибудь знает, как итеративно рассчитать эти значения?

Например, учитывая [1 2] в качестве входных данных, он должен найти и сохранить следующие списки:

[0 0], [10], [1 1], [1 2], [0 1], [0 2]

Спасибо!

Ответы [ 2 ]

4 голосов
/ 19 апреля 2010

Вот стандартный рекурсивный генератор: 

import java.util.Arrays;

//...

static void generate(int... limits) {
    generate(new int[limits.length], limits, 0);
}
static void generate(int[] arr, int[] limits, int n) {
    if (n == limits.length) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = 0; i <= limits[n]; i++) {
            arr[n] = i;
            generate(arr, limits, n + 1);
        }
    }
}

//....

generate(1, 2);
/* prints
[0, 0]
[0, 1]
[0, 2]
[1, 0]
[1, 1]
[1, 2]
*/

Это работает так же, как если бы вы написали переменное число вложенных циклов. С рекурсией вам нужно написать только один цикл, и он может иметь переменную глубину вложения (бесконечно, если вы не осторожны!).

Существует также итерационная, т.е. нерекурсивная версия: 

static void generateI(int... limits) {
    int[] arr = new int[limits.length];
    int n;
    do {
        System.out.println(Arrays.toString(arr));
        n = limits.length - 1;
        while (n >= 0 && arr[n] == limits[n]) {
            arr[n] = 0;
            n--;
        }
        if (n >= 0) arr[n]++;
    } while (n >= 0);
}

Это работает во многом так же, как приращение на 1 работает в двоичной арифметике (или на любой другой базе), за исключением того, что каждая позиция имеет свой предел.

Например, в базе 10 вот как вы увеличиваете: 

 12399
     ^ (is highest digit, therefore set to 0, move left)

 12390
    ^ (is highest digit, therefore set to 0, move left)

 12400
   ^ (not the highest digit, add 1, DONE!)
1 голос
/ 19 апреля 2010

Не похоже, что вы действительно хотите перестановок . Если вам дан массив X = [1, 2], его перестановками будут именно [1, 2] и [2, 1]. Следуя вашему примеру, вы хотите, чтобы он генерировал все кортежи z, где 0 <= z <= X. </p>

Эта проблема со списком кортежей хорошо решена с помощью решения полигенных смазок. Ваша заявленная проблема перестановок решена решением Фазаля.

...