Рубрики
Без рубрики

Перестановки массива в Java

Краткое и практическое руководство по созданию перестановок массивов на Java.

Автор оригинала: baeldung.

1. введение

В этой статье мы рассмотрим, как создавать перестановки массива .

Во-первых, мы определим, что такое перестановка. Во-вторых, мы рассмотрим некоторые ограничения. И в-третьих, мы рассмотрим три способа их вычисления: рекурсивно, итеративно и случайным образом.

Мы сосредоточимся на реализации на Java и поэтому не будем вдаваться в математические подробности.

2. Что такое Перестановка?

Перестановка множества – это перестановка его элементов. Набор, состоящий из n элементов, имеет n! перестановки. Здесь н! – это факториал, который является произведением всех положительных целых чисел, меньших или равных n .

2.1. Пример

Массив целых чисел [3,4,7] состоит из трех элементов и шести перестановок:

n!! x 2 x

Перестановки: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Ограничения

Число перестановок быстро увеличивается с n . Хотя для создания всех перестановок из десяти элементов требуется всего несколько секунд, для создания всех перестановок из 15 элементов потребуется две недели:

3. Алгоритмы

3.1. Рекурсивный алгоритм

Первый алгоритм, который мы рассмотрим, это Алгоритм кучи . Это рекурсивный алгоритм, который производит все перестановки путем замены одного элемента на итерацию.

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

public static  void printAllRecursive(
  int n, T[] elements, char delimiter) {

    if(n == 1) {
        printArray(elements, delimiter);
    } else {
        for(int i = 0; i < n-1; i++) {
            printAllRecursive(n - 1, elements, delimiter);
            if(n % 2 == 0) {
                swap(elements, i, n-1);
            } else {
                swap(elements, 0, n-1);
            }
        }
        printAllRecursive(n - 1, elements, delimiter);
    }
}

Метод использует два вспомогательных метода:

private void swap(T[] input, int a, int b) {
    T tmp = input[a];
    input[a] = input[b];
    input[b] = tmp;
}
private void printArray(T[] input) {
    System.out.print('\n');
    for(int i = 0; i < input.length; i++) {
        System.out.print(input[i]);
    }
}

Здесь мы записываем результат в System.out , однако вместо этого мы можем легко сохранить результат в массиве или в списке.

3.2. Итерационный алгоритм

Алгоритм кучи также может быть реализован с помощью итераций:

int[] indexes = new int[n];
int[] indexes = new int[n];
for (int i = 0; i < n; i++) {
    indexes[i] = 0;
}

printArray(elements, delimiter);

int i = 0;
while (i < n) {
    if (indexes[i] < i) {
        swap(elements, i % 2 == 0 ?  0: indexes[i], i);
        printArray(elements, delimiter);
        indexes[i]++;
        i = 0;
    }
    else {
        indexes[i] = 0;
        i++;
    }
}

3.3. Перестановки в лексикографическом порядке

Если элементы сопоставимы, мы можем генерировать перестановки, отсортированные по естественному порядку элементов:

public static > void printAllOrdered(
  T[] elements, char delimiter) {

    Arrays.sort(elements);
    boolean hasNext = true;

    while(hasNext) {
        printArray(elements, delimiter);
        int k = 0, l = 0;
        hasNext = false;
        for (int i = elements.length - 1; i > 0; i--) {
            if (elements[i].compareTo(elements[i - 1]) > 0) {
                k = i - 1;
                hasNext = true;
                break;
            }
        }

        for (int i = elements.length - 1; i > k; i--) {
            if (elements[i].compareTo(elements[k]) > 0) {
                l = i;
                break;
            }
        }

        swap(elements, k, l);
        Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length));
    }
}

Этот алгоритм имеет обратную операцию на каждой итерации, и поэтому он менее эффективен для массивов, чем алгоритм Кучи.

3.4. Рандомизированный алгоритм

Если n велико, мы можем сгенерировать случайную перестановку путем перетасовки массива:

Collections.shuffle(Arrays.asList(elements));

Мы можем сделать это несколько раз, чтобы сгенерировать выборку перестановок.

Мы можем создавать одни и те же перестановки несколько раз, однако при больших значениях n шансы сгенерировать одну и ту же перестановку дважды невелики.

4. Заключение

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

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

Реализацию всех фрагментов кода в этой статье можно найти в нашем репозитории Github .