Как итеративно вернуть все перестановки массива в двумерный массив? - PullRequest
Новая
       22

Как итеративно вернуть все перестановки массива в двумерный массив?

0 голосов
/ 17 июня 2019

Я пытаюсь написать программу, которая будет перебирать все возможные перестановки массива String и возвращать двумерный массив со всеми перестановками.В частности, я пытаюсь использовать массив строк длиной 4 для возврата двумерного массива с 24 строками и 4 столбцами.

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

Для того, что я хочу, чтобы код делал, я знаю, что заголовок должен быть: 

public class Permutation
{
     public String[][] arrayPermutation(String[] str)
     {
          //code to return 2D array
     }
}

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

Я очень новичок в программировании, и любая помощь будет принята с благодарностью.

1 Ответ

1 голос
/ 17 июня 2019

Ваша проблема перестановок - это в основном просто проблема перестановки индексов.Если вы можете упорядочить числа от 0 до n - 1 во всех возможных вариантах, вы можете использовать их в качестве индексов вашего входного массива и просто скопировать строки.Следующий алгоритм не является оптимальным, но он достаточно графический, чтобы объяснять и реализовывать итеративно. 

public static String[][] getAllPermutations(String[] str) {
    LinkedList<Integer> current = new LinkedList<>();
    LinkedList<Integer[]> permutations = new LinkedList<>();

    int length = str.length;
    current.add(-1);

    while (!current.isEmpty()) {
        // increment from the last position.
        int position = Integer.MAX_VALUE;
        position = getNextUnused(current, current.pop() + 1);
        while (position >= length && !current.isEmpty()) {
            position = getNextUnused(current, current.pop() + 1);
        }
        if (position < length) {
            current.push(position);
        } else {
            break;
        }

        // fill with all available indexes.
        while (current.size() < length) {
            // find first unused index.
            int unused = getNextUnused(current, 0);

            current.push(unused);
        }
        // record result row.
        permutations.add(current.toArray(new Integer[0]));
    }

    // select the right String, based on the index-permutation done before.
    int numPermutations = permutations.size();
    String[][] result = new String[numPermutations][length];
    for (int i = 0; i < numPermutations; ++i) {
        Integer[] indexes = permutations.get(i);
        String[] row = new String[length];
        for (int d = 0; d < length; ++d) {
            row[d] = str[indexes[d]];
        }
        result[i] = row;
    }

    return result;
}

public static int getNextUnused(LinkedList<Integer> used, Integer current) {
    int unused = current != null ? current : 0;
    while (used.contains(unused)) {
        ++unused;
    }
    return unused;
}

Метод getAllPermutations организован в части инициализации, цикле, собирающем все перестановки (числовые), и, наконец,преобразование найденной перестановки индекса в перестановки строк.

Поскольку преобразование из int в строку является тривиальным, я просто объясню часть коллекции.Цикл повторяется до тех пор, пока представление не полностью исчерпано или завершено изнутри.

Сначала мы увеличиваем представление (current).Для этого мы берем последнюю цифру и увеличиваем ее до следующего свободного значения.Затем мы выскакиваем, если мы выше длины, и смотрим на следующую цифру (и увеличиваем ее).Мы продолжаем это, пока не достигнем допустимого значения (ниже длины).

После этого мы заполняем оставшуюся часть цифр всеми оставшимися цифрами.После этого мы сохраняем текущее представление в списке массивов.

Этот алгоритм не является оптимальным с точки зрения времени выполнения!Куча быстрее.Но реализация Heap итеративно требует нетривиального стека, который утомителен для реализации / объяснения.

...