Советы по реализации алгоритма перестановки в Java

Поскольку вы заранее знаете количество перестановок (это N!), а также хотите/должны вернуть int[][], я бы выбрал массив напрямую. Вы можете объявить его в самом начале с правильными размерами и вернуть в конце. Таким образом, вам вообще не нужно беспокоиться о преобразовании его впоследствии.

Поскольку вы в значительной степени завершили его самостоятельно на javascript, я продолжу и дам вам код Java для реализации алгоритма перестановки Steinhaus. По сути, я просто перенес ваш код на Java, оставив как можно больше, включая комментарии.

Я протестировал его до N = 7. Я пытался вычислить N = 8, но он работает уже почти 10 минут на процессоре Intel Core 2 Duo с тактовой частотой 2 ГГц и все еще работает, лол.

Я уверен, что если бы вы действительно работали над этим, вы могли бы значительно ускорить это, но даже тогда вы, вероятно, сможете выжать из него только еще пару N-значений, если, конечно, у вас нет доступа к суперкомпьютер ;-).

Предупреждение - этот код правильный, НЕ надежный. Если вам нужна надежность, чего обычно не требуется для домашних заданий, то это будет упражнение, оставленное вам. Я бы также рекомендовал реализовать его с помощью коллекций Java просто потому, что это был бы отличный способ изучить все тонкости API коллекций.

Включено несколько «вспомогательных» методов, в том числе один для печати двумерного массива. Наслаждаться!

Обновление: 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");
  }
}

Массивы java не изменяемы (в том смысле, что вы не можете изменить их длину). Для прямого перевода этого рекурсивного алгоритма вы, вероятно, захотите использовать интерфейс List (и, возможно, реализацию LinkedList, поскольку вы хотите поместить числа посередине). Это List<List<Integer>>.

Остерегайтесь, факториал быстро растет: для N = 13 будет 13! перестановок, то есть 6 227 020 800. Но я думаю, вам нужно запускать его только для небольших значений.

Приведенный выше алгоритм довольно сложен, мое решение будет таким:

• создайте List<int[]> для хранения всех перестановок
• создайте один массив размера N и заполните его идентификатором ({1,2,3,...,N})
• программная функция, которая на месте создает следующую перестановку в лексикографическом порядке
• repeat this until you get the identity again:
  • put a copy of the array at the end of the list
  • вызовите метод, чтобы получить следующую перестановку.

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

Алгоритм вычисления следующей перестановки можно найти в Интернете. Вот, например

Используйте что хотите, массивы или списки, но не конвертируйте их - это только усложнит задачу. Я не могу сказать, что лучше, возможно, я бы выбрал ArrayList<int[]>, так как внешний список позволяет мне легко добавлять перестановки, а внутренний массив достаточно хорош. Это всего лишь дело вкуса (но обычно предпочтение отдается спискам, так как они гораздо более гибкие).

По совету Говарда я решил, что не хочу использовать ничего, кроме примитивного типа массива. Алгоритм, который я изначально выбрал, было сложно реализовать на 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;
}