#java #algorithm #permutation
#java #алгоритм #перестановка
Вопрос:
В рамках школьного проекта мне нужно написать функцию, которая будет принимать целое число N и возвращать двумерный массив каждой перестановки массива {0, 1, …, N-1}. Объявление будет выглядеть как public static int[][] перестановки (int N).
Алгоритм, описанный в http://www.usna.edu/Users/math/wdj/book/node156.html вот как я решил это реализовать.
Я довольно долго боролся с массивами и массивами ArrayLists и ArrayLists из ArrayLists, но до сих пор я был разочарован, особенно пытаясь преобразовать 2d ArrayList в 2d массив.
Итак, я написал это на javascript. Это работает:
function allPermutations(N) {
// base case
if (N == 2) return [[0,1], [1,0]];
else {
// start with all permutations of previous degree
var permutations = allPermutations(N-1);
// copy each permutation N times
for (var i = permutations.length*N-1; i >= 0; i--) {
if (i % N == 0) continue;
permutations.splice(Math.floor(i/N), 0, permutations[Math.floor(i/N)].slice(0));
}
// "weave" next number in
for (var i = 0, j = N-1, d = -1; i < permutations.length; i ) {
// insert number N-1 at index j
permutations[i].splice(j, 0, N-1);
// index j is N-1, N-2, N-3, ... , 1, 0; then 0, 1, 2, ... N-1; then N-1, N-2, etc.
j = d;
// at beginning or end of the row, switch weave direction
if (j < 0 || j >= N) {
d *= -1;
j = d;
}
}
return permutations;
}
}
Итак, какова наилучшая стратегия для переноса этого на Java? Могу ли я сделать это только с примитивными массивами? Нужен ли мне массив ArrayLists? Или массив списков ArrayLists? Или есть какой-то другой тип данных, который лучше? Что бы я ни использовал, мне нужно иметь возможность преобразовать это обратно в массив примитивных массивов.
Может быть, есть лучший алгоритм, который упростил бы это для меня…
Заранее благодарю вас за ваш совет!
Комментарии:
1.
allPermutations(1)будет повторяться до тех пор, пока не произойдетStackOverflow.2. Я тоже живу такой жизнью. Удачи, братан.
Ответ №1:
Поскольку вам заранее известно количество перестановок (это N!), а также вы хотите / должны вернуть int[][] , я бы обратился непосредственно к массиву. Вы можете объявить его в самом начале с правильными размерами и вернуть его в конце. Таким образом, вам вообще не придется беспокоиться о его последующем преобразовании.
Ответ №2:
Поскольку вы в значительной степени выполнили его самостоятельно на javascript, я продолжу и предоставлю вам Java-код для реализации алгоритма перестановки Штайнхауса. По сути, я просто портировал ваш код на Java, оставив в нем столько же, сколько смог, включая комментарии.
Я тестировал его до N = 7. Я пытался заставить его вычислить N = 8, но он работает уже почти 10 минут на процессоре Intel Core 2 Duo с частотой 2 ГГц и все еще работает, lol.
Я уверен, что если бы вы действительно работали над этим, вы могли бы значительно ускорить процесс, но даже тогда вы, вероятно, сможете выжать из него, возможно, еще пару N-значений, если, конечно, у вас нет доступа к суперкомпьютеру ;-).
Предупреждение — этот код корректен, но НЕ надежен. Если он вам нужен надежным, чего обычно не требуется для выполнения домашних заданий, то это упражнение остается за вами. Я бы также рекомендовал реализовать его с использованием Java Collections, просто потому, что это был бы отличный способ изучить входы и выходы из Collections API.
Включено несколько «вспомогательных» методов, в том числе один для печати 2d-массива. Наслаждайтесь!
Обновление: N = 8 заняло 25 минут 38 секунд.
Редактировать: Исправлено N == 1 и N == 2.
public class Test
{
public static void main (String[] args)
{
printArray (allPermutations (8));
}
public static int[][] allPermutations (int N)
{
// base case
if (N == 2)
{
return new int[][] {{1, 2}, {2, 1}};
}
else if (N > 2)
{
// start with all permutations of previous degree
int[][] permutations = allPermutations (N - 1);
for (int i = 0; i < factorial (N); i = N)
{
// copy each permutation N - 1 times
for (int j = 0; j < N - 1; j)
{
// similar to javascript's array.splice
permutations = insertRow (permutations, i, permutations [i]);
}
}
// "weave" next number in
for (int i = 0, j = N - 1, d = -1; i < permutations.length; i)
{
// insert number N at index j
// similar to javascript's array.splice
permutations = insertColumn (permutations, i, j, N);
// index j is N-1, N-2, N-3, ... , 1, 0; then 0, 1, 2, ... N-1; then N-1, N-2, etc.
j = d;
// at beginning or end of the row, switch weave direction
if (j < 0 || j > N - 1)
{
d *= -1;
j = d;
}
}
return permutations;
}
else
{
throw new IllegalArgumentException ("N must be >= 2");
}
}
private static void arrayDeepCopy (int[][] src, int srcRow, int[][] dest,
int destRow, int numOfRows)
{
for (int row = 0; row < numOfRows; row)
{
System.arraycopy (src [srcRow row], 0, dest [destRow row], 0,
src[row].length);
}
}
public static int factorial (int n)
{
return n == 1 ? 1 : n * factorial (n - 1);
}
private static int[][] insertColumn (int[][] src, int rowIndex,
int columnIndex, int columnValue)
{
int[][] dest = new int[src.length][0];
for (int i = 0; i < dest.length; i)
{
dest [i] = new int [src[i].length];
}
arrayDeepCopy (src, 0, dest, 0, src.length);
int numOfColumns = src[rowIndex].length;
int[] rowWithExtraColumn = new int [numOfColumns 1];
System.arraycopy (src [rowIndex], 0, rowWithExtraColumn, 0, columnIndex);
System.arraycopy (src [rowIndex], columnIndex, rowWithExtraColumn,
columnIndex 1, numOfColumns - columnIndex);
rowWithExtraColumn [columnIndex] = columnValue;
dest [rowIndex] = rowWithExtraColumn;
return dest;
}
private static int[][] insertRow (int[][] src, int rowIndex,
int[] rowElements)
{
int srcRows = src.length;
int srcCols = rowElements.length;
int[][] dest = new int [srcRows 1][srcCols];
arrayDeepCopy (src, 0, dest, 0, rowIndex);
arrayDeepCopy (src, rowIndex, dest, rowIndex 1, src.length - rowIndex);
System.arraycopy (rowElements, 0, dest [rowIndex], 0, rowElements.length);
return dest;
}
public static void printArray (int[][] array)
{
for (int row = 0; row < array.length; row)
{
for (int col = 0; col < array[row].length; col)
{
System.out.print (array [row][col] " ");
}
System.out.print ("n");
}
System.out.print ("n");
}
}
Ответ №3:
Массивы Java не изменяемы (в том смысле, что вы не можете изменить их длину). Для прямого перевода этого рекурсивного алгоритма вы, вероятно, захотите использовать интерфейс List (и, вероятно, реализацию LinkedList, поскольку вы хотите поместить числа в середину). Это List<List<Integer>> .
Остерегайтесь быстрого роста факториала: при N = 13 существует 13! перестановок, что равно 6 227 020 800. Но я думаю, вам нужно запускать его только для небольших значений.
Приведенный выше алгоритм довольно сложный, мое решение было бы:
- создайте
List<int[]>для хранения всех перестановок - создайте один массив размером N и заполните его идентификатором ({1,2,3, …,N})
- программная функция, которая на месте создает следующую перестановку в лексикографическом порядке
- повторяйте это, пока снова не получите идентификатор:
- поместите копию массива в конец списка
- вызовите метод, чтобы получить следующую перестановку.
Если вашей программе просто нужно вывести все перестановки, я бы не стал их сохранять и просто распечатал сразу.
Алгоритм для вычисления следующей перестановки можно найти в Интернете. Вот, например
Комментарии:
1. Хороший совет; это почти то, что я в итоге сделал. Я обнаружил, что лексикографический алгоритм намного проще реализовать на Java. Большое вам спасибо!
Ответ №4:
Используйте все, что хотите, массивы или списки, но не преобразуйте их — это только усложнит задачу. Я не могу сказать, что лучше, вероятно, я бы выбрал ArrayList<int[]> , поскольку внешний список позволяет мне легко добавлять перестановки, а внутренний массив достаточно хорош. Это просто дело вкуса (но обычно предпочитают списки, поскольку они намного более гибкие).
Ответ №5:
Следуя совету Говарда, я решил, что не хочу использовать ничего, кроме примитивного типа массива. Алгоритм, который я изначально выбрал, было непросто реализовать на Java, поэтому благодаря совету сталкера я выбрал алгоритм с лексикографическим порядком, описанный в Википедии. Вот что у меня получилось:
public static int[][] generatePermutations(int N) {
int[][] a = new int[factorial(N)][N];
for (int i = 0; i < N; i ) a[0][i] = i;
for (int i = 1; i < a.length; i ) {
a[i] = Arrays.copyOf(a[i-1], N);
int k, l;
for (k = N - 2; a[i][k] >= a[i][k 1]; k--);
for (l = N - 1; a[i][k] >= a[i][l]; l--);
swap(a[i], k, l);
for (int j = 1; k j < N-j; j ) swap(a[i], k j, N-j);
}
return a;
}
private static void swap(int[] is, int k, int l) {
int tmp_k = is[k];
int tmp_l = is[l];
is[k] = tmp_l;
is[l] = tmp_k;
}